Classes of graphs for which upper fractional domination equals independence, upper domination, and upper irredundance (Q1343143)

The authors consider finite simple graphs. For such a graph \(G= (V,E)\) the independence number \(\beta (G)\) is the maximum cardinality of a set of non-adjacent vertices. A set \(S\) of vertices is dominating if \(N[ S]= V\); and the upper domination number \(\Gamma (G)\) is the maximum cardinality over all minimal dominating sets. A vertex \(u\in S\subseteq V\) has a private neighbour \(w\) if \(w\in N[ S]\) and \(w\not\in N[S- \{u\}]\), and \(S\) is said to be irredundant if every vertex in \(S\) has a private neighbour. The upper irredundance number \(\text{IR} (G)\) is the maximum cardinality of an irredundant set of \(G\). A function \(f: V\to [0,1]\) is a dominating function if \(f(N [v]) \geq 1\) for each \(v\in V\), where, for a set \(S\) of vertices, \(f(S)= \sum_{v\in S} f(v)\). The dominating function \(f\) is minimal if for every other dominating function \(g\), one has \(f(v)\leq g(v)\) for each \(v\in V\). The maximum of \(f(V)\) over all minimal dominating functions \(f\) is the fractional domination number \(\Gamma_ f (G)\). The authors easily establish that \(\beta (G)\leq \Gamma(G) \leq \Gamma_ f(G)\leq \text{IR} (G)\) and survey the literature on the classes of graphs for which \(\beta (G)= \Gamma(G)= \text{IR} (G)\). The main contribution of the authors is that these equalities hold for the class of strongly perfect graphs. In fact, for strongly perfect graphs equality of the parameters holds not only for \(G\) but for all induced subgraphs of \(G\). It is observed that this stronger property does not hold for tristled graphs and upper bound graphs. The authors then pass on to study classes of graphs for which the equalities do not hold throughout. Among these are claw-free, dart-free, pan-free and \((K_ 4-e)\)-free Berge graphs, and unimodular, slender and slim graphs. All these graphs however satisfy \(\Gamma (G)= \Gamma_ f (G)\). The authors give two examples of graphs for which this equality does not hold. They also prove that if \({\mathcal T}\) is any of these four parameters then \({\mathcal T} (G_ 1+ G_ 2)= \max \{{\mathcal T} (G_ 1), {\mathcal T} (G_ 2)\}\) where \(G_ 1+ G_ 2\) is the join of the graphs \(G_ 1\) and \(G_ 2\).