A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs <s> Minimum Dominating Independent Set and Minimum Maximal Irredundant Set <s> Abstract A family of concepts involving maximum independent sets which have been under recent study are introduced. Interrelations among the concepts are pointed out and some recent relevant work is discussed. <s> BIB001 </s> A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs <s> Minimum Dominating Independent Set and Minimum Maximal Irredundant Set <s> In this dissertation, we focus on developing general NP-complete constructions and applying them to a number of related graph problems. We will present original NP-completeness results, some of which are new, and others which are simpler proofs of existing NP-completeness results (see Table 2 and Table 3 in Chapter 6). All of the proofs of these results are no longer than two pages; most are less than one page long. The great majority of these results use reductions from the Exact Cover by 3 Sets problem and use a common graph construction. The full generality of this technique has not been fully developed and we suggest a number of "open" problems that may be shown NP-complete by applying similar techniques. <s> BIB002 </s> A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs <s> Minimum Dominating Independent Set and Minimum Maximal Irredundant Set <s> A graph G is called well covered if every two maximal independent sets of G have the same number of vertices. In this paper, we characterize well covered simplicial, chordal and circular arc graphs. © 1996 John Wiley & Sons, Inc. <s> BIB003
These two parameters were introduced in section 4.7. The key to their complexity is the following result: is a hereditary hypergraph with no isolated vertices, then ir(Ω(H)) = γ(Ω(H)) = i(Ω(H))) = π(H) where π(H) is the smallest order of a partition of V into elements of E. In section 4.5, we have already seen that calculation of π(H) is NP-complete for H a hereditary hypergraph. Thus, γ, ir and i are NP-complete for representatives of hereditary hypergraphs, upper bound graphs, and simplicial graphs. Again in section 4.5, we recalled that for G a connected graph, γ(M (G)) = π(M (G)) = α 1 (G), and α 1 (G) can be calculated in time O(n 1.5 + e), where M (G) has n vertices and e edges. Thus, ir and i can be calculated in this same time. Now consider calculating i(L(G)), i.e. finding the size of a minimum sized maximal set of vertices of L(G) that is independent. In G, this will be a minimum sized maximal set of edges that are not incident, i.e., a minimum maximal matching. However, as we have already seen, the minimum maximal matching problem is NP-complete, so i is NP-complete for line graphs. McRae BIB002 shows that calculating ir(L(G)) is also NP-complete. Note that a graph is called well-covered BIB001 if all maximal independent sets have the same size, i.e., i(G) = β 0 (G). It turns out that the class of simplicial graphs that are also well-covered is the same as the class of vertex unisimplicial graphs BIB003 . Also, for the natural definition of a graph being fractionally wellcovered, a graph is vertex unisimplicial iff it is fractionally well-covered  . Vertex unisimplicial graphs have even more properties equal. This cannot be extended to the other related parameters as it is quite easy to find vertex unisimplicial graphs with ir(G) < γ(G) or with Γ(G) < IR(G).