On the well-coveredness of square graphs

Year 2022, Volume: 71 Issue: 2, 490 - 501, 30.06.2022

Zakir Deniz

https://doi.org/10.31801/cfsuasmas.910947

Abstract

The square of a graph G is obtained from G by putting an edge between two distinct vertices whenever their distance in G is 2. A graph is well-covered if every maximal independent set in the graph is of the same size. In this paper, we investigate the graphs whose squares are well-covered. We first provide a characterization of the trees whose squares are well-covered. Afterwards, we show that a bipartite graph G and its square are well-covered if and only if every component of G is $K_1$ or $K_{r,r}$ for some $r\ge 1$. Moreover, we obtain a characterization of the graphs whose squares are well-covered in the case $\alpha \left(G\right)=\alpha \left(G^2\right)+k$ for $k\in \{0,1\}$.

Keywords

Independent set, distance in graphs, well-covered

Supporting Institution

The Scientific and Technological Research Council of Turkey

Project Number

121F018

References

• Bacso, G., Tuza, Z., Dominating cliques in P5-free graphs, Periodica Mathematica Hungarica, 21 (4) (1990), 303–308, https://dx.doi.org/10.1007/bf02352694.
• Berge, C., Some Common Properties for Regularizable Graphs, Edge-Critical Graphs and B-graphs, Springer, 1981, https://dx.doi.org/10.1007/3-540-10704-5 10.
• Campbell, S., Ellingham, M., Royle, G., A characterization of well-covered cubic graphs, Journal of Combinatorial Computing, 13 (1993), 193–212.
• Demange, M., Ekim, T., Efficient recognition of equimatchable graphs, Information Processing Letters, 114 (1-2) (2014), 66–71, https://dx.doi.org/10.1016/j.ipl.2013.08.002.
• Ekim, T., Gozupek, D., Hujdurovic, A., Milanic, M., On almost well-covered graphs of girth at least 6., Discrete Mathematics and Theoretical Computer Science, 20 (2) (2018), 1i–1i, https://dx.doi.org/10.23638/DMTCS-20-2-17.
• Favaron, O., Very well covered graphs, Discrete Mathematics, 42 (2-3) (1982), 177–187, https://dx.doi.org/10.1016/0012-365X(82)90215-1.
• Finbow, A., Hartnell, B., Nowakowski, R. J., A characterization of well covered graphs of girth 5 or greater, Journal of Combinatorial Theory, Series B, 57 (1) (1993), 44–68, https://dx.doi.org/10.1006/jctb.1993.1005.
• Levit, V. E., Mandrescu, E., Square-stable and well-covered graphs, Acta Universitatis Apulensis, 10 (2005), 297–308.
• Levit, V. E., Mandrescu, E., On K¨onig–Egerv´ary graphs and square-stable graphs, Acta Univ. Apulensis, Special Issue (2009), 425–435.
• Levit, V. E., Mandrescu, E., When is G2 a K¨onig–Egerv´ary Graph?, Graphs and Combinatorics, 29 (5) (2013), 1453–1458, https://dx.doi.org/10.1007/s00373-012-1196-5.
• Plummer, M. D., Some covering concepts in graphs, Journal of Combinatorial Theory, 8 (1) (1970), 91–98, https://dx.doi.org/10.1016/S0021-9800(70)80011-4.
• Ravindra, G., Well-covered graphs, Journal of Combinatorics and System Sciences, 2 (1) (1977), 20–21.
• Staples, J. A. W., On Some Subclasses of Well-Covered Graphs, PhD thesis, Vanderbilt University, 1975.
• West, D. B., Introduction to Graph Theory, vol. 2, Prentice Hall Upper Saddle River, 2001