- Tytuł:
- On Well-Covered Direct Products
- Autorzy:
-
Kuenzel, Kirsti
Rall, Douglas F. - Powiązania:
- https://bibliotekanauki.pl/articles/32315158.pdf
- Data publikacji:
- 2022-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
well-covered graph
direct product of graphs
isolatable vertex - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2022, 42, 2; 627-640
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł