On co-well covered graphs
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
A graph $G$ is called a well covered graph if every maximal independent set in $G$ is maximum, and co-well covered graph if its complement is a well covered graph. We study some properties of a co-well covered graph and we characterize when the join, the corona product, and cartesian product are co-well covered graphs. Also we characterize when powers of trees and cycles are co-well covered graphs. The line graph of a graph which is co-well covered is also studied.
Abstract
A graph $G$ is called a well covered graph if every maximal independent set in $G$ is maximum, and co-well covered graph if its complement is a well covered graph. We study some properties of a co-well covered graph and we characterize when the join, the corona product, and cartesian product are co-well covered graphs. Also we characterize when powers of trees and cycles are co-well covered graphs. The line graph of a graph which is co-well covered is also studied.
참고문헌 (10)
- G. Agnarsson, "Graph Theory: modeling, applications, and algorithms" (2007), Pearson Prentice Hall
- E. Boros, "On CIS circulants", Discrete Math, 318, pp.78~95 (2014)[DOI]
- J. Brown, "Well-covered circulant graphs", Discrete Math, 311(4), pp.244~251 (2011)[DOI]
- J. L. Gross, "Discrete Mathematics and its Applications" (2004), CRC Press
- M. Lesk, "Equi-matchable graphs, in Graph theory and combinatorics (Cambridge, 1983)", pp.239~254 (1984), Academic Press
- M. D. Plummer, "Some covering concepts in graphs", J. Combinatorial Theory, 8, pp.91~98 (1970)
- M. D. Plummer, "Well-covered graphs: a survey", Quaestiones Math, 16(3), pp.253~287 (1993)
- G. Ravindra, "Well-covered graphs", J. Combin. Inform. System Sci, 2(1), pp.20~21 (1977)
- J. A. W. Staples, "On some subclasses of well-covered graphs", J. Graph Theory, 3(2), pp.197~204 (1979)[DOI]
- J. Topp, "On the well-coveredness of products of graphs", Ars Combin