On well-covered Cartesian products

2017/03/25 by Hartnell, Bert L., Rall, Douglas F., Wash, Kirsti
#05C65 #05C69 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1703.08716

Abstract

In 1970, Plummer defined a well-covered graph to be a graph G in which all maximal independent sets are in fact maximum. Later Hartnell and Rall showed that if the Cartesian product G \Box H is well-covered, then at least one of G or H is well-covered. In this paper, we consider the problem of classifying all well-covered Cartesian products. In particular, we show that if the Cartesian product of two nontrivial, connected graphs of girth at least 4 is well-covered, then at least one of the graphs is K₂. Moreover, we show that K₂ \Box K₂ and C₅ \Box K₂ are the only well-covered Cartesian products of nontrivial, connected graphs of girth at least 5.

Related

• On the Cartesian product of non well-covered graphs
• A characterization of well-dominated Cartesian products
• On well-covered direct products
• The Well-Covered Dimension of Products of Graphs
• On well-dominated direct, Cartesian and strong product graphs