5 added 26 characters in body

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$.

4 edited body

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 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 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 $v:=|V(G)|$. 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|=v-2m$. |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 $(v-2m)/m$. (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{v-2m}{m} 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 $$v 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$. 3 deleted 9 characters in body; added 163 characters in body 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 simple undirected 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$and the bound is achieved for frac{d+2}{2}\rceil$.

(b) For every $d \geq 1$ .there exists a 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 $v:=|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|=v-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 $(v-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{v-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 $$v \leq 2m + (d-m)m=(d+2-m)m \leq \lfloor\frac{d+2}{2} \rfloor \lceil \frac{d+2}{2}\rceil.$$

Finally, one

(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$.

2 deleted 329 characters in body
1