MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 4 down vote accepted

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

share|cite|improve this answer
Dear Sergey: thank you very much. I am actually very interested in the case $l=4$ and the best possible bound. The motivation is I want to understand certain associated primes of monomial ideals, and in special cases they correspond to antiholes, as you called it, so the more precise info the better. If you are interested in knowing more, let me know and I would be happy to tell you. – Hailong Dao May 27 '11 at 3:12
Dear Hailong: I changed the answer to a proof which works for all $l \geq 4$. Can the construction achieving the bound be realized in your setting, or, perhaps, there are some additional constraints? – Sergey Norin May 27 '11 at 18:49
Dear Sergey, thank you for the complete and elegant answer. I do have some other constraints, but I have to figure out how to translate them to graph theoretic terms. I will let you know if I have further questions. – Hailong Dao May 28 '11 at 5:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.