On the well-coveredness of square graphs

Authors : Zakir DENİZ

Pages : 490-501

Doi:10.31801/cfsuasmas.910947

View : 19 | Download : 9

Publication Date : 2022-06-30

Article Type : Research Paper

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 K1  or K r , r Kr,r for some r ≥ 1 r≥1 . Moreover, we obtain a characterization of the graphs whose squares are well-covered in the case α insert ignore into journalissuearticles values( G ); = α insert ignore into journalissuearticles values( G 2 ); + k αinsert ignore into journalissuearticles values(G);=αinsert ignore into journalissuearticles values(G2);+k αG=αG2+k αinsert ignore into journalissuearticles values(G);=αinsert ignore into journalissuearticles values(G);2+k for $k\in \{0,1\}$.
Keywords : Independent set, distance in graphs, well covered