On the well-coveredness of square graphs
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 K1K1 or Kr,rKr,r for some r≥1r≥1. Moreover, we obtain a characterization of the graphs whose squares are well-covered in the case α(G)=α(G2)+kα(G)=α(G2)+kαG=αG2+kα(G)=α(G)2+k for $k\in \{0,1\}$.
Keywords:
Independent set, distance in graphs well-covered,
___
- 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
- ISSN: 1303-5991
- Yayın Aralığı: Yılda 4 Sayı
- Başlangıç: 1948
- Yayıncı: Ankara Üniversitesi