Upper bounds on number of vertices of graphs whose complements has no induced cycles of certain lengths

2011-05-23T20:55:57Z

Let $G$ be a finite, simple, undirected, connected graph. Suppose that $G$ has maximal degree $d$ and the complement $G^c$ has no induced cycles of lengths $i$, for $4 \leq i \leq l$. My question is:

What are the best known upper bounds on the number of vertices $n(G)$ of $G$, if we fixed $d$ and $l$?

For example, if $l=4$ then the condition on $G$ says that $G$ has induced matching number $1$. It is easy to see that $G$ must have diameter at most $3$, so $n(G)$ is of order $d^3$ at best. It seems to me that such bound can be improved, yet I do not see how.

Answer by Sergey Norin for Upper bounds on number of vertices of graphs whose complements has no induced cycles of certain lengths

2011-05-26T21:22:03Z

Excluding induced matching of size $2$ appears to be the most restrictive condition and the bound is independent on $l$:

(a) Let $G$ be a connected graph with maximum degree $d$ and no induced matching of size $2$. Then $|V(G)| \leq \lfloor\frac{d+2}{2} \rfloor \lceil \frac{d+2}{2}\rceil$.

(b) For every $d \geq 1$ there exists a connected graph $G$ with maximum degree $d$, every induced cycle in the complement of $G$ of length $3$, and $|V(G)| = \lfloor\frac{d+2}{2} \rfloor \lceil \frac{d+2}{2}\rceil.$

(Updated 5/27/11 to extend the proof to $l=4$.)

Proof: (a) Let $M$ be a maximum (non-induced) matching in $G$ chosen so that the sum of degrees of vertices of $M$ in $G$ is minimal. Let $M$ consist of $m$ edges, let $X:=V(M)$ and let $Y:=V(G)-X$. Note that:

(i) $Y$ is an independent set. (Vertices of $Y$ are pairwise non-adjacent as $M$ is maximal.)

(ii) If $v \in Y$ is adjacent to $u \in X$ and $uw \in M$ is the matching edge incident to $u$ then $\deg(v) \geq \deg(w)$, as otherwise replacing $uw$ by $uv$ in $M$ decreases the sum of degrees of vertices in $M$.

(iii) For every $uw \in M$ at least $m-1$ edges incident with $u$ or $w$ have the other end in $X$, not counting $uw$. (There must be an edge between $uw$ and any other edge in $M$, as otherwise these two edges will form an induced matching.)

Let $n:=|V(G)|$. We use (i),(ii) and (iii) in a counting argument, which is described in terms of discharging as follows. Let every vertex in $Y$ start with a charge $1$. Then the total charge is $|Y|=n-2m$. In a discharging step let every vertex $v \in Y$ distribute its charge uniformly among its neighbors, which are all in $X$ by (i). (Every $v \in Y$ sends a charge $1/\deg(v)$ to each of its neighbors.)

The ends of some edge $uw \in M$ must as a result receive total charge at least $(n-2m)/m$. Let $d_1 :=\deg(u)$, $d_2 :=\deg(w)$ and suppose that $d_1 \geq d_2$, without loss of generality. By (ii) the charge that $u$ and $w$ receive from any single vertex in $Y$ is no greater than $1/d_2$. Finally, by (iii) there are at most $d_1+d_2 - 2 - (m-1)$ neighbors of $u$ and $w$ in $Y$. We get $$ \frac{n-2m}{m} \leq \frac{1}{d_2}\left( d_1+d_2 -m -1\right).$$ It is easy to see that the right side is maximized when $d_1=d$ and $d_2=1$. With these choices of degrees we have $$ n \leq 2m + (d-m)m=(d+2-m)m \leq \lfloor\frac{d+2}{2} \rfloor \lceil \frac{d+2}{2}\rceil.$$

(b) One can extract an example achieving the bound from the above argument. Let $G$ consist of a set of $\lfloor \frac{d+2}{2} \rfloor$ pairwise adjacent vertices, each of which is joined to $\lceil \frac{d}{2} \rceil$ additional degree one vertices. Then the complement of $G$ consists of a clique and $\lfloor \frac{d+2}{2} \rfloor$ pairwise non-adjacent vertices only having neighbors in this clique. From this description it is not hard to see that all induced cycles in the complement of $G$ are of length $3$.

Upper bounds on number of vertices of graphs whose complements has no induced cycles of certain lengths - MathOverflow

Upper bounds on number of vertices of graphs whose complements has no induced cycles of certain lengths

Answer by Sergey Norin for Upper bounds on number of vertices of graphs whose complements has no induced cycles of certain lengths