×

On the well-coveredness of Cartesian products of graphs. (English) Zbl 1229.05239

Summary: A graph \(G\) is well-covered if every maximal independent set has the same cardinality. This paper investigates when the Cartesian product of two graphs is well-covered. We prove that if \(G\) and \(H\) both belong to a large class of graphs that includes all non-well-covered triangle-free graphs and most well-covered triangle-free graphs, then \(G\times H\) is not well-covered. We also show that if \(G\) is not well-covered, then neither is \(G\times G\). Finally, we show that \(G\times G\) is not well-covered for all graphs of girth at least 5 by introducing super well-covered graphs and classifying all such graphs of girth at least 5.

MSC:

05C76 Graph operations (line graphs, products, etc.)
05C35 Extremal problems in graph theory
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Finbow, A.; Hartnell, B.; Nowakowski, R. J., A characterization of well-covered graphs of girth 5 or greater, J. Combin. Theory B, 57, 44-68 (1993) · Zbl 0777.05088
[2] Plummer, M. D., Some covering concepts in graphs, J. Combin. Theory, 8, 91-98 (1970) · Zbl 0195.25801
[3] Sankaranarayana, R. S.; Stewart, L. K., Complexity results for well-covered graphs, Networks, 22, 3, 247-262 (1992) · Zbl 0780.90104
[4] Tankus, D.; Tarsi, M., The Structure of well-covered graphs and the complexity of their recognition problems, J. Combin. Theory B, 69, 230-233 (1997) · Zbl 0873.05074
[5] Topp, J.; Volkmann, L., On the Well-coveredness of products of graphs, Ars Combin., 33, 199-215 (1992) · Zbl 0776.05090
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.