Premium
Maximal independent sets in graphs with at most r cycles
Author(s) -
Ying Goh Chee,
Meng Koh Khee,
Sagan Bruce E.,
Vatter Vincent R.
Publication year - 2006
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20185
Subject(s) - combinatorics , mathematics , indifference graph , chordal graph , pancyclic graph , maximal independent set , discrete mathematics , 1 planar graph , graph
We find the maximum number of maximal independent sets in two familiesof graphs. The first family consists of all graphs with n vertices and at most r cycles. The second family is all graphs of the first family which are connected and satisfy n ≥ 3 r . © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 270–282, 2006