On the well-coveredness of square graphs

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

1. 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.
2. 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.
3. Campbell, S., Ellingham, M., Royle, G., A characterization of well-covered cubic graphs, Journal of Combinatorial Computing, 13 (1993), 193–212.
4. 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.
5. 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.
6. 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.
7. 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.
8. Levit, V. E., Mandrescu, E., Square-stable and well-covered graphs, Acta Universitatis Apulensis, 10 (2005), 297–308.

9. Levit, V. E., Mandrescu, E., On K¨onig–Egerv´ary graphs and square-stable graphs, Acta Univ. Apulensis, Special Issue (2009), 425–435.
10. 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.
11. 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.
12. Ravindra, G., Well-covered graphs, Journal of Combinatorics and System Sciences, 2 (1) (1977), 20–21.
13. Staples, J. A. W., On Some Subclasses of Well-Covered Graphs, PhD thesis, Vanderbilt University, 1975.
14. West, D. B., Introduction to Graph Theory, vol. 2, Prentice Hall Upper Saddle River, 2001