A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs <s> Proof: <s> With every graph G (finite and undirected with no loops or multiple lines) there is associated a graph L ( G ), called the line-graph of G , whose points correspond in a one-to-one manner with the lines of G in such a way that two points of L ( G ) are adjacent if and only if the corresponding lines of G are adjacent. This concept was originated by Whitney ( 3 ). In a similar way one can associate with G another graph which we call its total graph and denote by T ( G ). This new graph has the property that a one-to-one correspondence can be established between its points and the elements (the set of points and lines) of G such that two points of T ( G ) are adjacent if and only if the corresponding elements of G are adjacent (if both elements are points or both are lines) or theyare incident <s> BIB001 </s> A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs <s> Proof: <s> We define a graph M(G) as an intersection graph @W(F) on the point set V(G) of any graph G. Let X(G) be the line set of G and F = V'(G) @? X(G), where V'(G) indicates the family of all one point subsets of the set V(G). Let M(G) = @W(F). M(G) is called the middle graph of G. The following theorems result: 1.Theorem 1. Let G be any graph and G^+ be a graph constructed from G. Then we have L(G^+)@?M(G), where L(G^+) is the line graphof G^+ 2.Theorem 2. Let G be a graph. The middle graph M(G) of G is hamiltonian if and only if G contains a closed spanning trail. 3.Theorem 3. If a graph G is eulerian, then the middle graph m(G) of G is eulerian and hamiltonian. 4.Theorem 4. If M(G) is eulerian, then G is eulerian and M(G) is hamiltonian. 5.Theorem 5. Let G be a graph. The middle graph M(G) of G contains a closed spanning trail if and only if G is connected and without points of degree =< 1. 6.Theorem 6. If a graph G is n-line connected, then the middle graph M(G) is n-connected. <s> BIB002 </s> A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs <s> Proof: <s> An undirected graph is trivially perfect if for every induced subgraph the stability number equals the number of (maximal) cliques. We characterize the trivially perfect graphs as a proper subclass of the triangulated graphs (thus disproving a claim of Buneman 3), and we relate them to some well-known classes of perfect graphs. <s> BIB003 </s> A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs <s> Proof: <s> Algorithmic Graph Theory and Perfect Graphs, first published in 1980, has become the classic introduction to the field. This new Annals edition continues to convey the message that intersection graph models are a necessary and important tool for solving real-world problems. It remains a stepping stone from which the reader may embark on one of many fascinating research trails. The past twenty years have been an amazingly fruitful period of research in algorithmic graph theory and structured families of graphs. Especially important have been the theory and applications of new intersection graph models such as generalizations of permutation graphs and interval graphs. These have lead to new families of perfect graphs and many algorithmic results. These are surveyed in the new Epilogue chapter in this second edition. New edition of the "Classic" book on the topic Wonderful introduction to a rich research area Leading author in the field of algorithmic graph theory Beautifully written for the new mathematician or computer scientist Comprehensive treatment <s> BIB004 </s> A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs <s> Proof: <s> Abstract A graph G is well-covered (or w-c) if every maximal independent set of points in G is also maximum. Clearly, this is equivalent to the property that the greedy algorithm for constructing a maximal independent set always results in a maximum independent set. Although the problem of independence number is well-known to be NP-complete, it is trivially polynomial for well-covered graphs. The concept of well-coveredness was introduced by the author in [P1] and was first discussed therein with respect to its relationship to a number of other properties involving the independence number. Since then, a number of results about well-covered graphs have been obtained. It is our purpose in this paper to survey these results for the first time. As the reader will see, many of the results we will discuss are quite recent and have not as yet appeared in print. <s> BIB005
Let HH be an arbitrary hereditary hypergraph, and G = Ω(HH). Let e = (x, y) be an arbitrary edge in G. Then x and y are edges in HH with x ∩ y = ∅. Let u ∈ x ∩ y. Since HH is hereditary, {u} is an edge in HH, and hence a vertex in G. In fact, {u} is a simplicial vertex in G, and e belongs to {u}'s simplex. Therefore, G is edge simplicial, and thus upper bound. 2 To see that representative graphs of hereditary hypergraphs are a proper subclass of upper bound graphs, note that K 1,3 is an upper bound graph but not the representative graph of any hereditary hypergraph. Of course, treating an edge as a set containing a pair of vertices, every graph G = (V, E) is a hypergraph so that hypergraphs are a generalization of graphs. Considering G as a hypergraph, the graph Ω(G) is defined. Ω(G) is commonly known as the line (or edge) graph of G and denoted by L(G). Also, G is called the root graph of L(G). Although a simple graph is not a hereditary hypergraph, there is a natural hereditary hypergraph HH(G) associated with every graph when every vertex is added to the edge collection as a singleton set. Thus for every graph G, we can obtain the graph Ω(HH(G)). It turns out  that Ω(HH(G)) ≈ M (G), where M (G) is the middle graph of G, and ≈ is graph isomorphism (see section 4.12). For a graph G = (V, E), the middle graph of G BIB002 is given by M (G) = (V ∪ E, E ′ ) where two vertices of M (G) are adjacent if they are incident in G, i.e., either they are two edges of G that share a vertex, or one is an edge of G and the other is a vertex that is one end of the edge. From Ω(HH(G)) ≈ M (G), it follows that the class of middle graphs is a subclass of the representative graphs of hereditary hypergraphs. Let G + be the graph obtained by adding to G n new vertices and n new edges where each new edge joins a distinct new vertex to a distinct vertex of G. Then it can be shown BIB002  Thus, the class of middle graphs is a subset of the class of line graphs. There are other characterizations of middle graphs. Let S(G) be the subdivision graph of G, i.e., the graph obtained by inserting a vertex into every edge of G. Now the middle graph of G can be obtained by adding the edges of L(G) into S(G)  . Alternately, the middle graph of G can be obtained by removing the edges of G from the total graph of G BIB001  . A final characterization of middle graphs is given by the following result: A graph G is a middle graph if and only if there exists simplices S 1 , S 2 , ..., S s of G satisfying the following conditions: .., S s is a partition of E(G), and (iii) every non-simplicial vertex lies in exactly two simplices. By analyzing M (G), it is clear that the vertices of a simplex of M (G) correspond to a vertex of G and its incident edges. In particular, if we associate a specific simplicial vertex of a simplex S of M (G) with vertex v of G, then the non-simplicial vertices of S must be edges incident to v in G and other simplicial vertices of S must be self-loops about v in G. Thus, if self-loops are not allowed in the root graph, in this lemma there should be a fourth condition: (iv) every simplex contains only one simplicial vertex. Henceforth, we will assume that this condition is included in this characterization of middle graphs. If self-loops and multiple edges are permitted in the root graph, the class will be called pseudomiddle. Similarly, a pseudoline graph is the line graph of a pseudograph. As a point of comparison, an alternate characterization of line graphs  is that a set of complete subgraphs can be found which partitions the edges and no vertex belongs to more than two of the subgraphs. For a middle graph, each complete subgraph must in addition be simplicial with exactly one simplicial vertex. In addition to middle graphs, there is another known subclass of representatives of hereditary hypergraphs. Given a graph G = (V, E), let I be the set of all independent sets in graph G. Then H = (V, I) is an hereditary hypergraph whose representative graph I(G) is called the independence graph of G. The set of all such graphs  is called the class of independence graphs. The middle graph of the hypergraph H = (V, E) is defined in  to be the intersection graph Ω(F ), where Naturally, if the hypergraph corresponds to a simple graph, i.e., it has no duplicate edges and each edge has size 2, this results in the standard middle graph of the graph. In the more general case, the class of middle graphs of hypergraphs is the same as the class of upper bound graphs. This follows from a theorem in  that G is the middle graph of a hypergraph iff G has an independent set of vertices such that the collection of closed neighbourhoods of these vertices forms a set of complete subgraphs which covers the edges of G. It is easy to see that the closed neighbourhoods are the simplices of the upper bound graph, and the independent set consists of one simplicial vertex per simplex. In order to put the graph classes being studied in a context, some further subclasses of simplicial graphs will be mentioned. The class of graphs where each vertex belongs to exactly one simplex, call them vertex unisimplicial graphs, have been studied in the literature BIB005 . (Note that in the community studying well-covered graphs, these graphs are called simplicial.) Obviously, vertex unisimplicial graphs are simplicial, but they are neither upper bound nor split unless they are disconnected or complete. It might seem that this class of graphs would have a very restricted structure, but for any graph G, G + is vertex unisimplicial. The edge unisimplicial graph class, where each edge belongs to exactly one simplex, can also be defined. These graphs are upper bound and contain middle graphs. However, they do not contain pseudomiddle graphs as multiple edges lead to edges in two simplices. A class of graphs that has many polynomial algorithms is the class of perfect graphs   . The classes considered here are only weakly related to perfect graphs. The line graph of a bipartite graph is both a perfect graph   and a line graph. Also, the subclass of perfect graphs called split graphs BIB004 is a subclass of simplicial graphs. To see this, recall that a graph is called split if its vertex set can be partitioned into two sets so that one set induces a complete graph and the other set is an independent set. As a result, each vertex of the independent set is a simplicial vertex. Also each vertex of the complete set is either incident to a vertex of the independent set (a simplicial vertex), or else its closed neighbourhood is the complete set of the partition so that it is itself a simplicial vertex. Another class of perfect graphs related to the classes studied here is the class of hereditary upper bound graphs. A graph is a hereditary upper bound graph if every induced subgraph is an upper bound graph   . An equivalent specification for this class is (cograph ∩ chordal) or (P 4 , C k )-free for k ≥ 4  BIB003 . Thus, the class is chordal BIB004 and perfect. Figure 1 contains a diagram of the containment relationships amongst these classes of graphs. This paper will emphasize the algorithmic properties of middle, representatives of hereditary hypergraphs, upper bound, simplicial, and line graphs (in bold in the diagram).