Maximal Independent Sets In Graphs With At Most r Cycles

Bruce E. Sagan Department of Mathematics Michigan State University East Lansing, MI 48824-1027 sagan@math.msu.edu www.math.msu.edu/~sagan and Vincent R. Vatter Department of Mathematics Rutgers University 110 Frelinghuysen Rd Piscataway, NJ 08854-8019 vatter@math.rutgers.edu

1. Introduction

2. Previous Results

3. The Main Theorem 1. Introduction

Let G = (V, E) be a simple graph. A subset I ⊆ V is independent if there are no edges between any two elements of I. Also, I is maximal if it is contained in no larger independent set. We let

m(G) = number of maximal independent sets in G.

Ex. The path P_{3}

[figure: P_{3} =; w; v; u]

has independent sets

I_{1} = {u, w}, I_{2} = {v}

so m(P_{3}) = 2.

Given a family F of graphs with |V | = n, we ask two questions

1. What is max_{G∈F} m(G)?

2. What are the extremal graphs?

1a. History

Given a family F of graphs with |V | = n, we ask two questions

1. What is max_{G∈F} m(G)?

2. What are the extremal graphs?

Erdös and Moser possed the original question for all graphs with n vertices in the early 1960s. (Actually, they posed it in terms of maximal cliques.) Below is a history of the questions that have been addressed concerning graphs with a bounded number of cycles.

F  Who  When Extremal?
all graphs  Erdös  ~1960  Y
all graphs  Moon and Moser  1965  Y
connected  Füredi  1987  N
connected  Griggs, Grinstead,
and Guichard  1988  Y
trees  Wilf  1986  N
trees  Sagan  1988  Y
≤ 1 cycle  Jou and Chang  1997  Y
≤ 2, 3 cycles Goh and Koh  2001  Y
≤ r cycles  Sagan and Vatter  2001  Y

2. Previous Results Let tG stand for the disjoint union of t copies of G. Define

G(n) := \{ \begin{matrix}\frac{n}{3}K_{3} & if n ≡ 0 (mod 3), \\ 2K_{2} ⊎ \frac{n−4}{3}K_{3} & if n ≡ 1 (mod 3), \\ K_{2} ⊎ \frac{n−2}{3}K_{3} & if n ≡ 2 (mod 3). \end{matrix}

Also let

G′(n) := K_{4} ⊎ \frac{n−4}{3}K_{3} if n ≡ 1 (mod 3).

Since m(G ⊎ H) = m(G)m(H), we see that

g(n) := m(G(n)) = \{ \begin{matrix}3^{\frac{n}{3}} & if n ≡ 0 (mod 3), \\ 4 · 3^{\frac{n−4}{3}} & if n ≡ 1 (mod 3), \\ 2 · 3^{\frac{n−2}{3}} & if n ≡ 2 (mod 3). \end{matrix}

Note that m(G′(n)) = m(G(n)). Theorem 1 (Moon and Moser) Let G be a graph with n ≥ 2 vertices. Then

m(G) ≤ g(n)

with equality if and only if G = G(n) or G′(n).

Construct a graph K_{m} ∗ G by picking a vertex v_{0} in K_{m} and connecting it to a single vertex in each component of G. If n ≥ 6 then let

C(n) := \{ \begin{matrix}K_{3} ∗ \frac{n−3}{3}K_{3} & if n ≡ 0 (mod 3), \\ K_{4} ∗ \frac{n−4}{3}K_{3} & if n ≡ 1 (mod 3), \\ K_{4} ∗ (K_{4} ⊎ \frac{n−8}{3}K_{3}) & if n ≡ 2 (mod 3). \end{matrix}

The graph C(14) is  [figure: v_{0}]

Letting c(n) := m(C(n)) we have

c(n) = \{ \begin{matrix}2 · 3^{\frac{n−3}{3}} + 2^{\frac{n−3}{3}} & if n ≡ 0 (mod 3), \\ 3^{\frac{n−1}{3}} + 2^{\frac{n−4}{3}} & if n ≡ 1 (mod 3), \\ 4 · 3^{\frac{n−5}{3}} + 3 · 2^{\frac{n−8}{3}} & if n ≡ 2 (mod 3). \end{matrix}

Theorem 2 (Griggs, Grinstead, and Guichard) Let G be a connected graph with n ≥ 6 vertices. Then

m(G) ≤ c(n)

with equality if and only if G = C(n).

The Main Theorem Now suppose that n ≥ 3r − 1. Define

G(n, r) := \{ \begin{matrix}rK_{3} ⊎ \frac{n−3r}{2}K_{2} & if n ≡ r (mod 2), \\ (r − 1)K_{3} ⊎ \frac{n−3r+3}{2} K_{2} & if n ≢ r (mod 2). \end{matrix}

Further, let g(n, r) := m(G(n, r)) and so

g(n, r) = \{ \begin{matrix}3^{r} · 2^{\frac{n−3r}{2}} & if n ≡ r(mod 2), \\ 3^{r−1} · 2^{\frac{n−3r+3}{2}} & if n ≢ r(mod 2). \end{matrix}

Now assume n ≥ 3r and define

C(n, r) := \{ \begin{matrix}K_{3} ∗ ((r − 1)K_{3} ⊎ \frac{n−3r}{2}K_{2}) & if n ≡ r (mod 2), \\ K_{1} ∗ (rK_{3} ⊎ \frac{n−3r−1}{2} K_{2}) & if n ≢ r (mod 2). \end{matrix}

As usual, we let c(n, r) := m(C(n, r)) and compute

c(n, r) = \{ \begin{matrix}3^{r−1} · 2^{\frac{n−3r+2}{2}} + 2^{r−1} & if n ≡ r(mod 2), \\ 3^{r} · 2^{\frac{n−3r−1}{2}} & if n ≢ r(mod 2). \end{matrix}

[figure: Define E to be the graph]

Theorem 3 (Sagan and Vatter) Let G be a graph with n vertices and at most r cycles where r ≥ 1.

(I) If n ≥ 3r − 1 then for all such graphs we have

m(G) ≤ g(n, r)

with equality if and only if G ≅ G(n, r).

(II) If n ≥ 3r then for all such graphs which are connected we have

m(G) ≤ c(n, r)

with equality if and only if G ≅ C(n, r) or if G is one of the following exceptional cases

n r possible G ≅ C̸(n, r)
4 1  P_{4}
5 1  C_{5}
7 2  C(7, 1), E

Proof (sketch) Consider the case of all graphs with n vertices and at most r cycles, n ≥ 3r − 1. Double induct on r and n, where the cases r ≤ 3 have been done previously. If n = 3r − 1 or 3r then

g(n, r) = g(n) and G(n, r) = G(n)

so we are done by Moon-Moser.

One can show that if G has two or more intersecting cycles then m(G) < g(n, r), so it suffices to look at graphs all of whose blocks are K_{2} or cycles. Let B be an endblock of G. We have three cases depending on whether B ≅ K_{2}, K_{3}, or C_{p} for p ≥ 4.

Let’s do B ≅ K_{2}. For any complete endblock B

m(G) = _{v∈V (B)}^{∑} m(G − N[v])

where N[v] is the closed neighborhood of v. Also, g(n, r) is monotonically inceasing in n. Now supposing V (B) = {v, w}, then both G − N[v] and G − N[w] have at most n − 2 vertices and at most r cycles. By induction and the above facts

m(G) ≤ 2g(n − 2, r) = g(n, r)

with equality iff G − N[v] = G − N[w] ≅ G(n − 2, r). It follows that B is actually a component of G isomorphic to K_{2} and so G ≅ G(n, r).