On well-covered direct products
Author(s) -
Kirsti Kuenzel,
Douglas F. Rall
Publication year - 2020
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.2296
Subject(s) - direct product , mathematics , combinatorics , vertex (graph theory) , graph , independence number , product (mathematics) , order (exchange) , cardinality (data modeling) , discrete mathematics , computer science , geometry , finance , economics , data mining
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 \times 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$.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom