On the Cartesian product of non well-covered graphs

2012/04/30 by Hartnell, Bert L., Rall, Douglas F.
#05C69 #05C76 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1204.6681

Abstract

A graph is well-covered if every maximal independent set has the same cardinality, namely the vertex independence number. We answer a question of Topp and Volkmann and prove that if the Cartesian product of two graphs is well-covered, then at least one of them must be well-covered.

Related

• On well-covered Cartesian products
• On well-covered direct products
• Well-covered and uniformly well-covered graphs
• On well-dominated graphs
• The Well-Covered Dimension of Products of Graphs