Upper bounds on number of vertices of graphs whose complements has no induced cycles of certain lengths - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T13:38:39Z http://mathoverflow.net/feeds/question/65797 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/65797/upper-bounds-on-number-of-vertices-of-graphs-whose-complements-has-no-induced-cyc Upper bounds on number of vertices of graphs whose complements has no induced cycles of certain lengths Hailong Dao 2011-05-23T20:55:57Z 2011-05-28T16:01:44Z <p>Let $G$ be a finite, simple, undirected, connected graph. Suppose that $G$ has maximal degree $d$ and the complement $G^c$ has no <em>induced</em> cycles of lengths $i$, for $4 \leq i \leq l$. My question is: </p> <blockquote> <p>What are the best known upper bounds on the number of vertices $n(G)$ of $G$, if we fixed $d$ and $l$? </p> </blockquote> <p>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. </p> http://mathoverflow.net/questions/65797/upper-bounds-on-number-of-vertices-of-graphs-whose-complements-has-no-induced-cyc/66112#66112 Answer by Sergey Norin for Upper bounds on number of vertices of graphs whose complements has no induced cycles of certain lengths Sergey Norin 2011-05-26T21:22:03Z 2011-05-28T16:01:44Z <p>Excluding induced matching of size $2$ appears to be the most restrictive condition and the bound is independent on $l$:</p> <blockquote> <p><strong>(a)</strong> 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$.</p> <p><strong>(b)</strong> 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.$</p> </blockquote> <p>(<strong>Updated 5/27/11</strong> to extend the proof to $l=4$.)</p> <p><strong>Proof: (a)</strong> 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:</p> <p><strong>(i)</strong> $Y$ is an independent set. (Vertices of $Y$ are pairwise non-adjacent as $M$ is maximal.)</p> <p><strong>(ii)</strong> 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$.</p> <p><strong>(iii)</strong> 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.)</p> <p>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.) </p> <p>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.$$</p> <p><strong>(b)</strong> 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$.</p>