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. 



Upper bounds on number of vertices of graphs whose complements has no induced cycles of certain lengths
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$.


