A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs <s> Maximum Minimal Dominating Set <s> This paper investigates cases where one graph parameter, upper fractional domination, is equal to three others: independence, upper domination and upper irredundance. We show that they are all equal for a large subclass, known as strongly perfect graphs, of the class of perfect graphs. They are also equal for odd cycles and upper bound graphs. However for simplicial graphs, upper irredundance might not equal the others, which are all equal. Also for many subclasses of perfect graphs other than the strongly perfect class, independence, upper domination and upper irredundance are not necessarily equal. We also show that if the graph join operation is used to combine two graphs which have some of the parameters equal, the resulting graph will have the same parameters equal. <s> BIB001 </s> A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs <s> Maximum Minimal Dominating 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
For any undirected graph G, there are six parameters that are related as follows  : γ(G) and β 0 (G) are the domination and independence numbers that we have already considered. i(G) is the size of a minimum (smallest) maximal independent set (a minimum dominating independent set), and Γ(G) is the size of a maximum (largest) minimal dominating set. For a set I and vertex v ∈ I, v is said to have itself as a private closed neighbour if v is not adjacent to any vertex of I; and v is said to have u as its private neighbour, if v is adjacent u, u / ∈ I and u is not adjacent to any other member of I. A set of vertices I is called irredundant if each member of I has a private (closed) neighbour, i.e., using the notation of Section 2, for all v ∈ I, is the size of a largest maximal (i.e., maximum) irredundant set, and ir(G) is the size of a minimum (smallest) maximal irredundant set. In this section, we consider Γ(G), and consider i(G), IR(G) and ir(G) in subsequent sections. The paper BIB001 showed that for upper bound graphs β 0 (G)) = Γ(G) = IR(G) = s, and for simplicial graphs β 0 (G)) = Γ(G) = s, with IR(G) not necessarily equal to the others. Thus, since it is easy to calculate the number of simplices s, Γ(G) is easily calculated for the class of simplicial graphs and descendants of this class. On the other hand, this is not true for line graphs as it has been shown BIB002 that the calculation of Γ(L(G)) is NP-complete.