% A AMStex file for a 3 page document
\magnification=\magstep1
\input amstex
\documentstyle{amsppt}
\loadbold
\TagsOnRight \hsize=160 true mm \vsize=220 true mm
\newcount\snumber
\def\nr #1{\the\snumber.#1}
\baselineskip=14 pt
\font\smcp=cmcsc8
\headline={\ifnum\pageno>1 {\smcp the electronic journal of combinatorics
2 (1995), \#N2\hfill\folio} \fi}

\define\Dk{\dot k}
\define\Du{\dot u}
\define\Dv{\dot v}
\define\Dw{\dot w}

\topmatter
\title The Independence Number of Dense Graphs with Large Odd Girth \endtitle

\leftheadtext{The Electronic Journal of Combinatorics 2 (1995) \#N2}
\rightheadtext{The Electronic Journal of Combinatorics 2 (1995) \#N2}

\affil James B. Shearer \\
Department of Mathematics\\
IBM T.J. Watson Research Center \\
Yorktown Heights, NY 10598 \\
JBS at WATSON.IBM.COM
\\
\vbox{\vskip .25in}
Submitted: January 31, 1995; Accepted: February 14, 1995 \endaffil




\endtopmatter

\document



%\baselineskip=16pt

{\bf 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 $\alpha (G)$ be the independence number of $G$.
Then we show $\alpha (G) \geq 2^{-\left(\frac{k-1}{k}\right)} \left[
\displaystyle{\sum_{v\in G}} d_1
(v)^{\frac{1}{k-1}} \right]^{(k-1)/k}$.  This improves and simplifies
results proven by Denley [1].

\vbox{\vskip .25in}

\noindent
{\bf AMS Subject Classification.}  05C35

\vbox{\vskip .50in}


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 $\alpha (G)$ be the independence number of $G$.
We will prove lower bounds for $\alpha (G)$ which improve and simplify
the results proven by Denley [1].

We will consider first the case $k=1$.
We need the following lemma.

\noindent
{\bf Lemma 1:}  Let $G$ be a triangle-free graph.
Then
$$
\alpha (G) \geq \sum_{v \in G} d_1 (v) / [1 + d_1 (v) + d_2 (v)] .
$$

\noindent
{\bf 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 $\displaystyle{\sum_{v \in 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.

We can now prove the following theorem.

\noindent
{\bf Theorem 1.} Suppose $G$ contains no 3 or 5 cycles.
Let $\bar d$ be the average degree of vertices of $G$.  Then
$$
\alpha (G) \geq \sqrt{n \bar d / 2} .
$$

\noindent
{\bf Proof.}  Since $G$ contains no 3 or 5 cycles, we have
$\alpha (G) \geq d_1 (v)$ (consider the neighbors of $v$) and
$\alpha (G) \geq 1 + d_2 (v)$ (consider $v$ and the points at distance
2 from $v$) for any vertex $v$ of $G$.  Hence
$\alpha (G) \geq \displaystyle{\sum_{v\in G}} d_1 (v) / [1 + d_1 (v)
+ d_2 (v)] \geq
\displaystyle{\sum_{v\in G}} d_1 (v) / 2 \alpha (G)$ (by lemma 1 and the
preceding remark).
Therefore $\alpha (G)^2 \geq n \bar d / 2$ or $\alpha (G) \geq
\sqrt {n \bar d 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.

\noindent
{\bf Lemma 2:}  Let $G$ have odd girth $2k+1$ or greater
$(k\geq 2)$.
Then
$$
\alpha (G) \geq \sum_{v \in G}
\frac{\frac12 ( 1+ d_1 (v) + \cdots + d_{k-1} (v) )}{1 + d_1 (v)
+ \cdots + d_k (v)} .
$$

\noindent
{\bf 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 \cup B$ is
$\displaystyle{\sum_{v \in G}} \frac{(1 + d_1 (v) + \cdots +
d_{k-1} (v))}{1 + d_1 (v) + \cdots + d_k (v)}$.
The lemma follows at once.

\noindent
{\bf Theorem 2:}  Let $G$ have odd girth $2k+3$ or greater $(k\geq 2)$.
Then
$$
\alpha (G) \geq 2^{- \left( \frac{k-1}{k} \right)} \left[ \sum_{v \in G}
d_1 (v)^{\frac{1}{k-1}} \right]^{\frac{k-1}{k}}  .
$$

\noindent
{\bf Proof.}  By Lemmas 1, 2
$$
\split
\alpha (G) \geq \sum_{v \in G} \left[
\left[ \frac{d_1 (v)}{1 +d_1 (v) +d_2 (v)} \right] \right. & + \frac12
\left[ \frac{1+d_1 (v) + d_2 (v)}{1+ d_1 (v) + d_2 (v) + d_3 (v)}
\right] \\
+ \cdots & + \frac12 \left. \left[ \frac{1 +d_1 (v) + \cdots + d_{k-1}
(v)}{1 + d_1 (v) + \cdots + d_k (v)} \right] \right] / (k-1) . \endsplit
$$
Since the arithmetic mean is greater than the geometric mean, we
can conclude that $\alpha (G) \geq \displaystyle{\sum_{v \in G}}
\left[ \frac{d_1 (v)
2^{-(k-2)}}{1+d_1 (v) + \cdots + d_k(v)} \right]^{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 \alpha (G)
\geq 1 + d_1 (v) + \cdots + d_k (v)$.
Hence $\alpha (G) \geq
\displaystyle{\sum_{v\in G}} \left[ \frac{d_1(v)}{2^{k-1} \alpha (G)}
\right]^{\frac{1}{k-1}}$
or $\alpha (G)^{\frac{k}{k-1}} \geq \frac12 \left[
\displaystyle{\sum_{v\in G}} d_1(v)^{\frac{1}{k-1}} \right]$ or
$\alpha (G) \geq 2^{-(\frac{k-1}{k})} \left[
\displaystyle{\sum_{v\in G}} d_1(v)^{\frac{1}{k-1}}
\right]^{\frac{k-1}{k}}$ as claimed.

\noindent
{\bf Corollary 1:}  Let $G$ be regular degree $d$ and odd girth
$2k + 3$ or greater $(k \geq 2 )$.  Then
$$
\alpha (G) \geq
2^{- \left( \frac{k-1}{k} \right)} n^{\frac{k-1}{k}} d^{\frac{1}{k}} .
$$

\noindent
{\bf Proof.}  Immediate from Theorem 3.

This improves Denley's Theorem 4.

\vbox{\vskip 0.1in}

\Refs \widestnumber \key{1}


\ref
\no 1 \by Denley, T.
\paper The Independence number of graphs with large odd girth
\jour The Electronic Journal of Combinatorics {\bf 1} (1994) \#R9
\endref


\endRefs

\enddocument




.