On Graphs Having Maximal Independent Sets of Exactly t Distinct Cardinalities
Tóm tắt
For a given positive integer t we consider graphs having maximal independent sets of precisely t distinct cardinalities and restrict our attention to those that have no vertices of degree one. In the situation when t is four or larger and the length of the shortest cycle is at least 6t − 6, we completely characterize such graphs.
Tài liệu tham khảo
Barbosa R, Hartnell BL: Some problems based on the relative sizes of the maximal independent sets in a graph. Congr. Numer. 131, 115–121 (1998)
Barbosa R, Hartnell BL: The effect of vertex and edge deletion on the number of sizes of maximal independent sets. J. Combin. Math. Combin. Comput. 70, 111–116 (2009)
Finbow AS, Hartnell BL: A game related to covering by stars. Ars Combin. 16, 189–198 (1983)
Finbow A, Hartnell B, Nowakowski RJ: A characterization of well-covered graphs of girth 5 or greater. J. Combin. Theory Ser. B 57, 44–68 (1993)
Finbow A, Hartnell B, Whitehead C: A characterization of graphs of girth eight or more with exactly two sizes of maximal independent sets. Discrete Math. 125, 153–167 (1994)
Plummer MD: Well-covered graphs. J. Combin. Theory 8, 91–98 (1970)