Geodesic
On Well-Covered Direct Products
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 627-640.

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2022_42_2_a17,
     author = {Kuenzel, Kirsti and Rall, Douglas F.},
     title = {On {Well-Covered} {Direct} {Products}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {627--640},
     publisher = {mathdoc},
     volume = {42},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a17/}
}
TY  - JOUR
AU  - Kuenzel, Kirsti
AU  - Rall, Douglas F.
TI  - On Well-Covered Direct Products
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 627
EP  - 640
VL  - 42
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a17/
LA  - en
ID  - DMGT_2022_42_2_a17
ER  - 
%0 Journal Article
%A Kuenzel, Kirsti
%A Rall, Douglas F.
%T On Well-Covered Direct Products
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 627-640
%V 42
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a17/
%G en
%F DMGT_2022_42_2_a17
Kuenzel, Kirsti; Rall, Douglas F. On Well-Covered Direct Products. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 627-640. http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a17/

[1] C. Berge, Some common properties for regularizable graphs, edge-critical graphs and B-graphs, in: Graph Theory and Algorithms, Proc. Sympos., Res. Inst. Electr. Comm., Tohoku Univ., Sendai, 1980, (Lecture Notes in Comput. Sci. 108, Springer, Berlin-New York 1981) 108–123. https://doi.org/10.1007/3-540-10704-5_10

[2] S.R. Campbell, M.N. Ellingham and G.F. Royle, A characterisation of well-covered cubic graphs, J. Combin. Math. Combin. Comput. 13 (1993) 193–212.

[3] O. Favaron, Very well covered graphs, Discrete Math. 42 (1982) 177–187. https://doi.org/10.1016/0012-365X(82)90215-1

[4] A. Finbow, B.L. Hartnell and R.J. Nowakowski, A characterization of well covered graphs of girth 5 or greater, J. Combin. Theory Ser. B 57 (1993) 44–68. https://doi.org/10.1006/jctb.1993.1005

[5] A. Finbow, B.L. Hartnell and R.J. Nowakowski, A characterization of well-covered graphs that contain neither 4 - nor 5 -cycles, J. Graph Theory 18 (1994) 713–721. https://doi.org/10.1002/jgt.3190180707

[6] A. Finbow, B.L. Hartnell, R.J. Nowakowski and M.D. Plummer, On well-covered triangulations: Part I, Discrete Appl. Math. 132 (2003) 97–108. https://doi.org/10.1016/S0166-218X(03)00393-7

[7] A. Finbow, B.L. Hartnell, R.J. Nowakowski and M.D. Plummer, On well-covered triangulations: Part II, Discrete Appl. Math. 157 (2009) 2799–2817. https://doi.org/10.1016/j.dam.2009.03.014

[8] A. Finbow, B.L. Hartnell, R.J. Nowakowski and M.D. Plummer, On well-covered triangulations: Part III, Discrete Appl. Math. 158 (2010) 894–912. https://doi.org/10.1016/j.dam.2009.08.002

[9] A. Finbow, B.L. Hartnell, R.J. Nowakowski and M.D. Plummer, Well-covered triangulations: Part IV, Discrete Appl. Math. 215 (2016) 71–94. https://doi.org/10.1016/j.dam.2016.06.030

[10] A.O. Fradkin, On the well-coveredness of Cartesian products of graphs, Discrete Math. 309 (2009) 238–246. https://doi.org/10.1016/j.disc.2007.12.083

[11] B.L. Hartnell and D.F. Rall, On the Cartesian product of non well-covered graphs, Electron. J. Combin. 20 (2013) #P21. https://doi.org/10.37236/2299

[12] B.L. Hartnell, D.F. Rall and K. Wash, On well-covered Cartesian products, Graphs Combin. 34 (2018) 1259–1268. https://doi.org/10.1007/s00373-018-1943-3

[13] P.K. Jha and G. Slutzki, Independence numbers of product graphs, Appl. Math. Lett. 7 (1994) 91–94. https://doi.org/10.1016/0893-9659(94)90018-3

[14] R.J. Nowakowski and D.F. Rall, Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16 (1996) 53–79. https://doi.org/10.7151/dmgt.1023

[15] M.D. Plummer, Some covering concepts in graphs, J. Combin. Theory 8 (1970) 91–98. https://doi.org/10.1016/S0021-9800(70)80011-4

[16] J. Topp and L. Volkmann, On the well-coveredness of products of graphs, Ars Combin. 33 (1992) 199–215.

[17] D.B. West, Introduction to Graph Theory (Prentice Hall, Inc., Upper Saddle River, New Jersey, 1996).