{C_2t+1,C≥l}-禁止图的边极值问题研究

Research on Extremal Problems of Edges in {C_2t+1,C≥l}-Free Graphs

摘要: Turán问题是极值图论中的核心研究课题之一。令F表示由一些图组成的集族，如果对任意的F∈F，图G都不包含F作为子图，则称图G是F-禁止图。将Turán数ex(n,F)定义为n个顶点的F-禁止图中的最大边数。令C_2t+1表示长度为2t+1的圈，P_t表示一条长度为l的路，C_≥l表示由长度大于等于l的所有的圈构成的集族。本文主要研究了{C_2t+1,C_≥l}-禁止图以及{C_2t+1,P_t}-禁止图的Turán数，当l>4t-2时，证明了。当l>4t-2为奇数且 时，证明了 。

Abstract: Turán problem is one of the central topics in extremal graph theory. Let F be a family of graphs. If for any F∈F , G does not contain F as a subgraph, then we say G is F-free. The Turán number ex(n,F) is defined as the maximum number of edges in an F-free graph on n vertices. Let C_2t+1 denote a cycle of length 2t+1 , let C_≥l denote a family of cycles with lengths from l to n and let P_t denote a path of length l. In the present paper, we study the Turán number for {C_2t+1,C_≥l} -free graphs and {C_2t+1,P_t} -free graphs. For l>4t-2 , we determine that . For is odd and , we prove that .

1. 引言

设 $G\left(V,E\right)$ 是一个简单无向图，其中V和E分别表示图G的顶点集和边集。用 $e\left(G\right)$ 表示图G的边集大小。令H是一个图，若 $V\left(H\right)\subseteq V\left(G\right)$ ， $E\left(H\right)\subseteq E\left(G\right)$ ，则称H是G的一个子图。令 $\mathcal{F}$ 表示由一些图组成的集族，如果对任意的 $F\in \mathcal{F}$ ，图G都不包含F作为子图，那么称图G是 $\mathcal{F}$ -禁止图。Turán数 $ex\left(n\text{,}\mathcal{F}\right)$ 定义为n个顶点的 $\mathcal{F}$ -禁止图中的最大边数。如果集族 $\mathcal{F}$ 仅包含一个简单图F，则我们可以将 $ex\left(n\text{,}\mathcal{F}\right)$ 简写为 $ex\left(n,F\right)$ 。关于Turán数现在已经有大量的研究，详见相关文献 [1] - [12] 。

设 $G_1$ 和 $G_2$ 是图G的两个不相交的子图， $G_1\cup G_2$ 表示 $G_1$ 和 $G_2$ 的并图，其顶点集为 $V\left(G_1\right)\cup V\left(G_2\right)$ ，边集为 $E\left(G\right)=E\left(G_1\right)\cup E\left(G_2\right)$ 。 $G_1\vee G_2$ 表示 $G_1$ 和 $G_2$ 的联图，其顶点集为 $V\left(G_1\right)\cup V\left(G_2\right)$ ，边集为 $E\left(G\right)=E\left(G_1\right)\cup E\left(G_2\right)\cup \left\{xy|x\in V\left(G_1\right),y\in V\left(G_2\right)\right\}$ 。 $K_n$ 表示n个顶点的完全图， $E_n$ 表示n个顶点的空图。令 $T_r\left(n\right)$ 表示n个顶点的Turán图，即含有n个顶点的完全r部图且每个部集的大小为 $\lceil \frac{n}{r}\rceil$ 或 $\lfloor \frac{n}{r}\rfloor$ 。

1907年，Mantel [7] 证明了以下定理：

定理1.1. 若G是n个顶点的 $K_3$ -禁止图，则

$ex\left(n,K_3\right)=\lfloor \frac{n^2}{4}\rfloor .$

同时，二部Turán图是唯一的可以达到边极值的图。

1941年，Turán [9] 证明了Turán图是唯一一个达到最大边数的 $K_{r+1}$ 禁止图。

定理1.2.对于 $n\ge r+1$ ， $r\ge 2$ ，

$ex\left(n,K_{r+1}\right)=e\left(T_r\left(n\right)\right).$

Erdős和Gallai [3] 在1959年证明了 $P_{\mathcal{l}}$ 的图兰数上界。

定理1.3. 若 $n\ge \mathcal{l}+1$ ，则

$ex\left(n,P_{\mathcal{l}}\right)=\frac{\left(\mathcal{l}-2\right)n}{2}.$

当 $\mathcal{l}-1$ 整除n时， $\frac{n}{\mathcal{l}-1}$ 个点不交的 $K_{\mathcal{l}-1}$ 的并是取到等号的一个图。

Faudree和Schelp [13] 以及Kopylov [14] 确定了对于任意的n的值， $ex\left(n,P_{\mathcal{l}}\right)$ 的精确值，并且刻画了对应的极图。

定理1.4. 令 $n=q\left(\mathcal{l}-1\right)+r$ ， $0\le r\le \mathcal{l}-2$ ，且 $\mathcal{l}\ge 2$ ，则

$ex\left(n,P_{\mathcal{l}}\right)=q\left(\begin{array}{c}\mathcal{l}-1\\ 2\end{array}\right)+\left(\begin{array}{c}r\\ 2\end{array}\right).$

相应的极图为 $q{K}_{\mathcal{l}-1}\cup K_r$ ，即q个点不交的 $K_{\mathcal{l}-1}$ 和一个 $K_r$ 的并。当 $\mathcal{l}$ 是偶数且同时r是 $\frac{\mathcal{l}}{2}$ 或者 $\frac{\mathcal{l}}{2}-1$ ，极图为 $t\left(0\le t<q\right)$ 个点不交的 $K_{\mathcal{l}-1}$ 和一个H的并，其中H为 $K_{\frac{\mathcal{l}}{2}-1}\vee K_{n-t\left(\mathcal{l}-1\right)-\frac{\mathcal{l}}{2}+1}$ 。

Erdős和Gallai [3] 在1959年证明了 ${\mathcal{C}}_{\ge \mathcal{l}}$ 的图兰数上界。

定理1.5. 对于 $n\ge \mathcal{l}$ ，

$ex\left(n,{\mathcal{C}}_{\ge \mathcal{l}}\right)\le \frac{\left(\mathcal{l}-1\right)\left(n-1\right)}{2}.$

当 $\mathcal{l}-2$ 整除 $n-1$ 时， $\frac{n-1}{\mathcal{l}-2}$ 个 $K_{\mathcal{l}-1}$ 共用一个点的图是取到等号的一个图。

Woodall [15] 在1976年以及Kopylov [14] 在1977年独立地证明了 $ex\left(n,{\mathcal{C}}_{\ge \mathcal{l}}\right)$ 的精确值。

定理1.6. 令 $n=q\left(\mathcal{l}-2\right)+r$ ， $1\le r\le \mathcal{l}-2$ ，且 $\mathcal{l}\ge 3$ ， $q\ge 1$ ，则

$ex\left(n,{\mathcal{C}}_{\ge \mathcal{l}}\right)=q\left(\begin{array}{c}\mathcal{l}-1\\ 2\end{array}\right)+\left(\begin{array}{c}r\\ 2\end{array}\right).$

2015年，Füredi和Gunderson [16] 研究了奇圈的图兰数，并且给出了以下定理：

定理1.7. 对 $n\ge 1$ ， $2k+1\ge 5$ ，

$ex\left(n,C_{2k+1}\right)=\{\begin{array}{ll}\left(\begin{array}{c}n\\ 2\end{array}\right)\hfill & n\le 2k,\hfill \\ g\left(n,k\right)\hfill & 2k+1\le n\le 4k-1\hfill \\ \lfloor \frac{n^2}{4}\rfloor \hfill & n\ge 4k-2.\hfill \end{array},$

其中，当 $n=\left(s-1\right)\left(2k-1\right)+r$ ，且 $s\ge 1$ ， $2\le r\le 2k$ ，s和r都是整数时，

$g\left(n,k\right)=\left(s-1\right)\left(\begin{array}{c}2k\\ 2\end{array}\right)+\left(\begin{array}{c}r\\ 2\end{array}\right).$

在本文中，我们研究了n个点的 $\left\{C_{2t+1},{\mathcal{C}}_{\ge \mathcal{l}}\right\}$ -禁止图，以及当 $\mathcal{l}$ 为奇数时 $\left\{C_{2t+1},P_{\mathcal{l}}\right\}$ -禁止图的最大边数。

定理1.8. 对于 $n\ge \mathcal{l}>4t-2$ ，则

$ex\left(n\text{,}\left\{C_{2t+1},{\mathcal{C}}_{\ge \mathcal{l}}\right\}\right)=\lfloor \frac{\mathcal{l}-1}{2}\rfloor \left(n-\lfloor \frac{\mathcal{l}-1}{2}\rfloor \right).$

注意到当 $n\le \mathcal{l}$ 时，根据定理1.7和1.8可以推出 $ex\left(n\text{,}\left\{C_{2t+1},{\mathcal{C}}_{\ge \mathcal{l}}\right\}\right)=ex\left(n,C_{2t+1}\right)$ 。显然， $E_{\lfloor \frac{\mathcal{l}-1}{2}\rfloor }\vee E_{n-\lfloor \frac{\mathcal{l}-1}{2}\rfloor }$ 是一个 $\left\{C_{2t+1},{\mathcal{C}}_{\ge \mathcal{l}}\right\}$ -禁止图，定理1.8证明了 $E_{\lfloor \frac{\mathcal{l}-1}{2}\rfloor }\vee E_{n-\lfloor \frac{\mathcal{l}-1}{2}\rfloor }$ 是一个边数最多的 $\left\{C_{2t+1},{\mathcal{C}}_{\ge \mathcal{l}}\right\}$ -禁止图。

定理1.9. 对于 $n\ge \mathcal{l}\ge 4t-2$ ，则

$ex\left(n\text{,}\left\{C_{2t+1},P_{\mathcal{l}}\right\}\right)=\lfloor \frac{\mathcal{l}-1}{2}\rfloor \left(n-\lfloor \frac{\mathcal{l}-1}{2}\rfloor \right).$

注意到当 $n\le \mathcal{l}$ 时，根据定理1.7和1.9可以推出 $ex\left(n\text{,}\left\{C_{2t+1},P_{\mathcal{l}}\right\}\right)=ex\left(n,C_{2t+1}\right)$ 。显然， $E_{\lfloor \frac{\mathcal{l}-1}{2}\rfloor }\vee E_{n-\lfloor \frac{\mathcal{l}-1}{2}\rfloor }$ 是一个 $\left\{C_{2t+1},P_{\mathcal{l}}\right\}$ -禁止图，定理1.9证明了 $E_{\lfloor \frac{\mathcal{l}-1}{2}\rfloor }\vee E_{n-\lfloor \frac{\mathcal{l}-1}{2}\rfloor }$ 是一个边数最多的 $\left\{C_{2t+1},P_{\mathcal{l}}\right\}$ -禁止图。

下面让我们回顾证明中需要用到的符号和引理。对于任意的 $X\subseteq V\left(G\right)$ ，用 $G\left[X\right]$ 表示由顶点集合X和边集合

$E\left(X\right)=\left\{uv\in E\left(G\right):u,v\in X\right\}$

构成的子图。令 $G-X=G\left[V\left(G\right)\backslash X\right]$ ，用

$N_G\left(X\right)=\left\{v\in V\left(G\right):\exists u\in X,uv\in E\left(G\right)\right\}$

表示G中与X中顶点相邻的所有顶点的集合。我们将 $N_G\left(\left\{x\right\}\right)$ 简写为 $N_G\left(x\right)$ 。图G顶点x的度 ${\mathrm{deg}}_G\left(x\right)$ 表示 $N_G\left(x\right)$ 的大小。在不会引起混淆的情况下，我们通常将省略下标。我们用 $\delta \left(G\right)$ 表示图G中顶点度的最小值。图G的周长 $c\left(G\right)$ 定义为G中最长圈的长度。

Dirac [17] 在1952年证明了下面的引理。

引理1.1. 若G是一个n个点的二连通图，则

$c\left(G\right)\ge \min \left\{2\delta \left(G\right),n\right\}.$

本文结构安排如下：在第二节中，我们证明了定理1.8。在第三节中，我们证明了定理1.9。

2. 定理1.8的证明

本节中，我们对 $\left\{C_{2t+1},{\mathcal{C}}_{\ge \mathcal{l}}\right\}$ -禁止图 $\left(\mathcal{l}>4t-2\right)$ 的最大边数问题进行研究。

定理1.8的证明令G为一个n个顶点的 $\left\{C_{2t+1},{\mathcal{C}}_{\ge \mathcal{l}}\right\}$ -禁止图。

情况1： $\mathcal{l}=2k+1$ 。

我们对n进行归纳。当 $n=2k$ 时，由于 $2k\ge 4t-2$ ，根据定理1.7可得

$e\left(G\right)\le ex\left(2k,C_{2t+1}\right)=k^2.$

现假设定理1.8在 $2k,2k+1,\cdots ,n-1\ge \mathcal{l}-1$ 时结论都成立，下面证明结论对n成立。

若G不是连通的，不妨设 $G_1$ 是G的含有 $n_1$ 个顶点的连通分支，则由归纳假设可知

$\begin{array}{c}e\left(G\right)=e\left(G_1\right)+e\left(G-V\left(G_1\right)\right)\\ \le \lfloor \frac{\mathcal{l}-1}{2}\rfloor \left(n_1-\lfloor \frac{\mathcal{l}-1}{2}\rfloor \right)+\lfloor \frac{\mathcal{l}-1}{2}\rfloor \left(n-n_1-\lfloor \frac{\mathcal{l}-1}{2}\rfloor \right)\\ \le \lfloor \frac{\mathcal{l}-1}{2}\rfloor \left(n-\lfloor \frac{\mathcal{l}-1}{2}\rfloor \right).\end{array}$

若G不是二连通的，不妨设 $G_1$ 是G的含有 $n_1$ 个顶点的二连通分支，同样由归纳假设可知

$\begin{array}{c}e\left(G\right)=e\left(G_1\right)+e\left(G-V\left(G_1\right)\right)\\ \le \lfloor \frac{\mathcal{l}-1}{2}\rfloor \left(n_1-\lfloor \frac{\mathcal{l}-1}{2}\rfloor \right)+\lfloor \frac{\mathcal{l}-1}{2}\rfloor \left(n-n_1+1-\lfloor \frac{\mathcal{l}-1}{2}\rfloor \right)\\ \le \lfloor \frac{\mathcal{l}-1}{2}\rfloor \left(n-\lfloor \frac{\mathcal{l}-1}{2}\rfloor \right).\end{array}$

若G是二连通的，当 $n\ge 2k+1$ 时，若存在一个点v，使得 $\mathrm{deg}\left(v\right)\le k$ ，则

$e\left(G\right)=e\left(G-v\right)+\mathrm{deg}\left(v\right)\le k\left(n-1-k\right)+k=k\left(n-k\right)=\lfloor \frac{\mathcal{l}-1}{2}\rfloor \left(n-\lfloor \frac{\mathcal{l}-1}{2}\rfloor \right).$

若 $\delta \left(G\right)\ge k+1$ ，根据引理1.1可知 $c\left(G\right)\ge \min \left\{2\delta \left(G\right),n\right\}\ge 2k+1$ ，即图G一定包含一个长度大于等于 $2k+1$ 的圈，矛盾。

情况2： $\mathcal{l}=2k$ 。

我们对n进行归纳。当 $n=2k-1$ 时，由于 $2k-1\ge 4t-2$ ，根据定理1.7可得

$e\left(G\right)\le ex\left(2k-1,C_{2t+1}\right)=k\left(k-1\right).$

现假设定理1.8在 $2k-1,2k,\cdots ,n-1\ge \mathcal{l}-1$ 时结论都成立，下面证明结论对n成立。

若G不连通或一连通，则类似情况1.中的证明，仍可得

$e\left(G\right)=\lfloor \frac{\mathcal{l}-1}{2}\rfloor \left(n-\lfloor \frac{\mathcal{l}-1}{2}\rfloor \right).$

若G是二连通的，当 $n\ge 2k$ 时，若存在一个点v，使得 $\mathrm{deg}\left(v\right)\le k-1$ ，则

$\begin{array}{c}e\left(G\right)=e\left(G-v\right)+\mathrm{deg}\left(v\right)\\ \le \left(k-1\right)\left(n-1-k+1\right)+k-1\\ =\left(k-1\right)\left(n-k+1\right)\\ =\lfloor \frac{\mathcal{l}-1}{2}\rfloor \left(n-\lfloor \frac{\mathcal{l}-1}{2}\rfloor \right).\end{array}$

若 $\delta \left(G\right)\ge k$ ，根据引理1.1可知 $c\left(G\right)\ge \min \left\{2\delta \left(G\right),n\right\}\ge 2k$ ，即图G一定包含一个长度大于等于2k

的圈，矛盾。

3. 定理1.9的证明

类似于定理1.8的证明，我们利用数学归纳法来对 $\mathcal{l}$ 为奇数时的 $\left\{C_{2t+1},P_{\mathcal{l}}\right\}$ -禁止图 $\left(\mathcal{l}\ge 4t-2\right)$ 的边数的上界进行估计。

定理1.9的证明 令G为一个n个顶点的 $\left\{C_{2t+1},P_{\mathcal{l}}\right\}$ -禁止图。当 $\mathcal{l}$ 为奇数，令 $\mathcal{l}=2k+1$ 。

我们对n进行归纳。当 $n=2k+1$ 时，由于 $2k+1\ge 4t-2$ ，根据定理1.7可得

$e\left(G\right)\le ex\left(2k,C_{2t+1}\right)=k^2.$

现假设定理1.9在 $2k+1,2k+2,\cdots ,n-1\ge \mathcal{l}-1$ 时结论都成立，下面证明结论对n成立。

若G不是连通的，不妨设 $G_1$ 是G的含有 $n_1$ 个顶点的连通分支，则由归纳假设可知

$\begin{array}{c}e\left(G\right)=e\left(G_1\right)+e\left(G-V\left(G_1\right)\right)\\ \le \lfloor \frac{\mathcal{l}-1}{2}\rfloor \left(n_1-\lfloor \frac{\mathcal{l}-1}{2}\rfloor \right)+\lfloor \frac{\mathcal{l}-1}{2}\rfloor \left(n-n_1-\lfloor \frac{\mathcal{l}-1}{2}\rfloor \right)\\ \le \lfloor \frac{\mathcal{l}-1}{2}\rfloor \left(n-\lfloor \frac{\mathcal{l}-1}{2}\rfloor \right).\end{array}$

若G不是二连通的，不妨设 $G_1$ 是G的含有 $n_1$ 个顶点的二连通分支，同样由归纳假设可知

$\begin{array}{c}e\left(G\right)=e\left(G_1\right)+e\left(G-V\left(G_1\right)\right)\\ \le \lfloor \frac{\mathcal{l}-1}{2}\rfloor \left(n_1-\lfloor \frac{\mathcal{l}-1}{2}\rfloor \right)+\lfloor \frac{\mathcal{l}-1}{2}\rfloor \left(n-n_1+1-\lfloor \frac{\mathcal{l}-1}{2}\rfloor \right)\\ \le \lfloor \frac{\mathcal{l}-1}{2}\rfloor \left(n-\lfloor \frac{\mathcal{l}-1}{2}\rfloor \right).\end{array}$

若G是二连通的，当 $n\ge 2k+2$ 时，若存在一个点v，使得 $\mathrm{deg}\left(v\right)\le k$ ，则

$e\left(G\right)=e\left(G-v\right)+\mathrm{deg}\left(v\right)\le k\left(n-1-k\right)+k=k\left(n-k\right)=\lfloor \frac{\mathcal{l}-1}{2}\rfloor \left(n-\lfloor \frac{\mathcal{l}-1}{2}\rfloor \right).$

若 $\delta \left(G\right)\ge k+1$ ，根据引理1.1可知 $c\left(G\right)\ge \min \left\{2\delta \left(G\right),n\right\}\ge 2k+2$ ，则图G一定包含一条长度为 $c\left(G\right)-1\ge 2k+1$ 的路，矛盾。

4. 结论

本文主要利用数学归纳法研究具有n个顶点的 $\left\{C_{2t+1},{\mathcal{C}}_{\ge \mathcal{l}}\right\}$ -禁止图，文中给出了n个顶点的 $\left\{C_{2t+1},{\mathcal{C}}_{\ge \mathcal{l}}\right\}$ -禁止图的边数的上界。此外，文中还对任意n个顶点的 $\left\{C_{2t+1},P_{\mathcal{l}}\right\}$ -禁止图，当 $\mathcal{l}$ 为奇数时，给出了 $\left\{C_{2t+1},P_{\mathcal{l}}\right\}$

-禁止图的边数的一个上界。

NOTES

^*通讯作者。