Abstract

Maximal Independent Sets In Graphs With At Most r Cycles

Vince Vatter
Mon Apr. 19 at 1:10pm in the Graduate Student Lounge

Around 1960, Erdos and independently Moon and Moser found the maximum number of maximal independent sets that a graph on n vertices could have and characterized the extremal graphs. In the late 1980s, Furedi found the same maximum for connected graphs while Griggs, Grinstead, and Guichard independently found this maximum and characterized the extremal graphs. Wilf then found this maximum for trees while Sagan characterized the extremal trees, Jou and Chang did the case of graphs with at most 1 cycle, and Goh and Koh did the cases of graphs with at most 2 and at most 3 cycles.

We find the maximum number of maximal independent sets in two families of graphs: all graphs with n vertices and at most r cycles, and all such graphs which are also connected, proving a conjecture of Goh and Koh. In addition, we characterize the extremal graphs. This is joint work with Bruce Sagan.