Article in volume
Authors:
Title:
On well-covered direct products
PDFSource:
Discussiones Mathematicae Graph Theory 42(2) (2022) 627-640
Received: 2019-01-09 , Revised: 2020-01-06 , Accepted: 2020-01-06 , Available online: 2020-01-27 , https://doi.org/10.7151/dmgt.2296
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
References:
- 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 - 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.
- O. Favaron, Very well covered graphs, Discrete Math. 42 (1982) 177–187.
https://doi.org/10.1016/0012-365X(82)90215-1 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - J. Topp and L. Volkmann, On the well-coveredness of products of graphs, Ars Combin. 33 (1992) 199–215.
- D.B. West, Introduction to Graph Theory (Prentice Hall, Inc., Upper Saddle River, New Jersey, 1996).
Close