Levit, Vadim E.; Mandrescu, Eugen Well-covered and Koenig-Egervary graphs. (English) Zbl 0952.05062 Congr. Numerantium 130, 209-218 (1998). 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\). Cited in 1 ReviewCited in 14 Documents MSC: 05C75 Structural characterization of families of graphs 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) Keywords:well-covered graph; very well-covered graph; stability number; Koenig-Egervary graph; matching Citations:Zbl 0195.25801; Zbl 0507.05053; Zbl 0404.05034; Zbl 0777.05088 PDFBibTeX XMLCite \textit{V. E. Levit} and \textit{E. Mandrescu}, Congr. Numerantium 130, 209--218 (1998; Zbl 0952.05062) Full Text: arXiv