THE INDEPENDENCE NUMBER OF DENSE

GRAPHS WITH LARGE ODD GIRTH

James B. Shearer Department of Mathematics IBM T.J. Watson Research Center Yorktown Heights, NY 10598 JBS at WATSON.IBM.COM

Submitted: January 31, 1995; Accepted: February 14, 1995

Abstract. Let G be a graph with n vertices and odd girth 2k + 3. Let the degree of a vertex v of G be d_{1}(v). Let α(G) be the independence number of G. Then we show

α(G) ≥ 2^{−(\frac{k−1}{k})} [∑_{v∈G}d_{1}(v)^{\frac{1}{k−1}} ]^{(k−1)/k}. This improves and simplifies results proven by

Denley [1].

AMS Subject Classification. 05C35

Let G be a graph with n vertices and odd girth 2k + 3. Let d_{i}(v) be the number of points of degree i from a vertex v. Let α(G) be the independence number of G. We will prove lower bounds for α(G) which improve and simplify the results proven by Denley [1].

We will consider first the case k = 1. We need the following lemma. Lemma 1: Let G be a triangle-free graph. Then

α(G) ≥ ∑_{v∈G} d_{1}(v)/[1 + d_{1}(v) + d_{2}(v)].

Proof. Randomly label the vertices of G with a permutation of the integers from 1 to n. Let A be the set of vertices v such that the minimum label on vertices at distance 0, 1 or 2 from v is on a vertex at distance 1. Clearly the probability that A contains a vertex v is d_{1}(v)/[1+d_{1}(v)+d_{2}(v)]. Hence the expected size of A is ∑_{v∈G}d_{1}(v)/[1+d_{1}(v)+d_{2}(v)].

Furthermore, A must be an independent set since if A contains an edge it is easy to see that it must lie in a triangle of G a contradiction. The result follows at once.

Typeset by AMS-TEX

We can now prove the following theorem. Theorem 1. Suppose G contains no 3 or 5 cycles. Let d̄ be the average degree of vertices of G. Then

α(G) ≥ \sqrt{nd̄/2}.

Proof. Since G contains no 3 or 5 cycles, we have α(G) ≥ d_{1}(v) (consider the neighbors of v) and α(G) ≥ 1 + d_{2}(v) (consider v and the points at distance 2 from v) for any vertex v of G. Hence α(G) ≥ ∑_{v∈G}d_{1}(v)/[1+d_{1}(v)+d_{2}(v)] ≥ ∑_{v∈G}d_{1}(v)/2α(G) (by lemma

1 and the preceding remark). Therefore α(G)^{2} ≥ nd̄/2 or α(G) ≥ \sqrt{nd̄2} as claimed.

This improves Denley’s Theorems 1 and 2. It is sharp for the regular complete bipartite graphs K_{aa}.

The above results are readily extended to graphs of larger odd girth. Lemma 2: Let G have odd girth 2k + 1 or greater (k ≥ 2). Then

α(G) ≥ ∑_{v∈G} \frac{\frac{1}{2}(1 + d_{1}(v) + ⋯ + d_{k−1}(v))}{1 + d_{1}(v) + ⋯ + d_{k}(v)}.

Proof. Randomly label the vertices of G with a permutation of the integers from 1 to n. Let A (respectively B) be the set of vertices v of G such that the minimum label on vertices at distance k or less from v is at even (respectively odd) distance k − 1 or less. It is easy to see that A and B are independent sets and that the expected size of A ∪ B

is ∑_{v∈G} \frac{(1 + d_{1}(v) + ⋯ + d_{k−1}(v))}{1 + d_{1}(v) + ⋯ + d_{k}(v)}. The lemma follows at once.

Theorem 2: Let G have odd girth 2k + 3 or greater (k ≥ 2). Then

α(G) ≥ 2^{−(\frac{k−1}{k})} [∑_{v∈G} d_{1}(v)^{\frac{1}{k−1}} ]^{\frac{k−1}{k}} .

Proof. By Lemmas 1, 2

α(G) ≥ ∑_{v∈G} [[\frac{d_{1}(v)}{1 + d_{1}(v) + d_{2}(v)}] + \frac{1}{2} [\frac{1 + d_{1}(v) + d_{2}(v)}{1 + d_{1}(v) + d_{2}(v) + d_{3}(v)}]

+ ⋯ + \frac{1}{2} [\frac{1 + d_{1}(v) + ⋯ + d_{k−1}(v)}{1 + d_{1}(v) + ⋯ + d_{k}(v)}]] /(k − 1).

Since the arithmetic mean is greater than the geometric mean, we can conclude that

α(G) ≥ ∑_{v∈G} [\frac{d_{1}(v)2^{−(k−2)}}{1 + d_{1}(v) + ⋯ + d_{k}(v)}]^{1/k−1}. Since the points at even (odd) distance

less than or equal k from any vertex v in G form independent sets we have 2α(G) ≥ 1 +

the electronic journal of combinatorics 2 (1995), #N2 3

d_{1}(v) + ⋯ + d_{k}(v). Hence α(G) ≥ ∑_{v∈G} [\frac{d_{1}(v)}{2^{k−1}α(G)}]^{\frac{1}{k−1}} or α(G)^{\frac{k}{k−1}} ≥ \frac{1}{2} [∑_{v∈G}d_{1}(v)^{\frac{1}{k−1}} ]

or α(G) ≥ 2^{−( \frac{k−1}{k})} [∑_{v∈G}d_{1}(v)^{\frac{1}{k−1}} ]^{\frac{k−1}{k}} as claimed.

Corollary 1: Let G be regular degree d and odd girth 2k + 3 or greater (k ≥ 2). Then

α(G) ≥ 2^{−(\frac{k−1}{k})}n^{\frac{k−1}{k}} d^{\frac{1}{k}} .

Proof. Immediate from Theorem 3.

This improves Denley’s Theorem 4.

References

1. Denley, T., The Independence number of graphs with large odd girth, The Electronic Journal of Combinatorics 1 (1994) #R9.