On Well-Covered Direct Products

Abstract

A graph G is well-covered if all maximal independent sets of G have the same cardinality. In 1992 Topp and Volkmann investigated the structure of well-covered graphs that have nontrivial factorizations with respect to some of the standard graph products. In particular, they showed that both factors of a well-covered direct product are also well-covered and proved that the direct product of two complete graphs (respectively, two cycles) is well-covered precisely when they have the same order (respectively, both have order 3 or 4). Furthermore, they proved that the direct product of two well-covered graphs with independence number one-half their order is well-covered. We initiate a characterization of nontrivial connected well-covered graphs G and H, whose independence numbers are strictly less than one-half their orders, such that their direct product G × H is well-covered. In particular, we show that in this case both G and H have girth 3 and we present several infinite families of such well-covered direct products. Moreover, we show that if G is a factor of any well-covered direct product, then G is a complete graph unless it is possible to create an isolated vertex by removing the closed neighborhood of some independent set of vertices in G.

Keywords

• well-covered graph
• direct product of graphs
• isolatable vertex
• 05c69
• 05c76