×

Stability, domination and irredundance in a graph. (English) Zbl 0612.05056

The author’s abstract: ”In a graph G, a set X is called a stable set if any two vertices of X are nonadjacent. A set X is called a dominating set if every vertex of V-X is joined to at least one vertex of X. A set X is called an irredundant set if every vertex of X, not isolated in X, has at least one proper neighbor, that is a vertex of V-X joined to it but to no other vertex of X. Let \(\alpha\) ’ are \(\alpha\), \(\gamma\), and \(\Gamma\), ir and IR, denote respectively the minimum and maximum cardinalities of a maximal stable set, a minimal dominating set, and a maximal irredundant set. It is known that ir\(\leq \gamma \leq \alpha '\leq \alpha \leq \Gamma \leq IR\) and that if G does not contain any induced subgraph isomorphic to \(K_{1,3}\), then \(\gamma =\alpha '\). Here we prove that if G contains no induced subgraph isomorphic to \(K_{1,3}\) or to the graph H of figure 1, then \(ir=\gamma =\alpha '\). We prove also that if G contains no induced subgraph isomorphic to \(K_{1,3}\), to H, or to the graph h of figure 3, then \(\Gamma =IR\). Finally, we improve a result of Bollobas and Cockayne about sufficient conditions for \(\gamma =ir\) in terms of forbidden subgraphs.”
Reviewer: R.L.Hemminger

MSC:

05C99 Graph theory
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allan, Discrete Math 23 pp 73– (1978)
[2] Graphs and Hypergraphs, North Holland, Amsterdam (1973).
[3] Bollobas, Graph Theory 3 pp 241– (1979)
[4] Cockayne, Discrete Math 33 pp 249– (1981)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.