Maximal independent sets in graphs with at most r cycles

Goh Chee Ying, Koh Khee Meng, Bruce E. Sagan, Vincent R. Vatter

Research output: Contribution to journalArticlepeer-review

Abstract

We find the maximum number of maximal independent sets in two families of 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 >= 3r. (C) 2006 Wiley Periodicals, Inc.

Original languageEnglish
Pages (from-to)270-282
Number of pages13
JournalJournal of Graph Theory
Volume53
DOIs
Publication statusPublished - Dec 2006

Keywords

  • cycle
  • ear decomposition
  • maximal independent set
  • NUMBER

Fingerprint

Dive into the research topics of 'Maximal independent sets in graphs with at most r cycles'. Together they form a unique fingerprint.

Cite this