5
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ May 27, 2011 at 3:12
  • $\begingroup$ 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? $\endgroup$ May 27, 2011 at 18:49
  • $\begingroup$ 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. $\endgroup$ May 28, 2011 at 5:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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