×

Well-covered and Koenig-Egervary graphs. (English) Zbl 0952.05062

Summary: A graph \(G= (V,E)\) is said to be well-covered [see M. D. Plummer, J. Comb. Theory 8, 91-98 (1970; Zbl 0195.25801)] if all its maximal stable sets have the same cardinality, namely, the stability number \(\alpha(G)\). If in addition \(|V|= 2\alpha(G)\), then \(G\) is very well-covered [see O. Favaron, Discrete Math. 42, 177-187 (1982; Zbl 0507.05053)]. \(G\) is called a Koenig-Egervary graph [see R. W. Deming, Discrete Math. 27, 23-33 (1979; Zbl 0404.05034)] if \(\alpha(G)+ \mu(G)=|V|\), where \(\mu(G)\) is the maximum cardinality of a matching of \(G\). In this paper we show that: (i) a connected Koenig-Egervary graph is well-covered if and only if it is very well-covered; (ii) a connected graph \(G\) is very well-covered if and only if \(G\) is a well-covered Koenig-Egervary graph. We also extend a result of A. Finbow, B. Hartnell and R. J. Nowakowski [J. Comb. Theory, Ser. B 57, No. 1, 44-68 (1993; Zbl 0777.05088)], proving that a graph \(G\), of girth \(\geq 8\) or \(G\neq C_7\) and of girth \(\geq 6\), is well-covered if and only if it is a Koenig-Egervary graph with exactly \(\alpha(G)\) pendant vertices, and \(\alpha(G)\) is insensitive to adding of any edge to \(G\).

MSC:

05C75 Structural characterization of families of graphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: arXiv