{C2t+1,C≥l}-禁止图的边极值问题研究 Research on Extremal Problems of Edges in {C2t+1,C≥l}-Free Graphs

doi:10.12677/AAM.2023.122078

Advances in Applied Mathematics
Vol. 12 No. 02 ( 2023 ), Article ID: 61935 , 7 pages
10.12677/AAM.2023.122078

${C_{2 t + 1}, C_{\geq l}}$ -禁止图的边极值问题研究

傅凌婷，王健^*，武彩萍

●How to Cite this Article

太原理工大学数学学院，山西晋中

收稿日期：2023年1月26日；录用日期：2023年2月19日；发布日期：2023年2月28日

摘要

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

关键词

图兰数， $F$ -禁止图，路和圈

Research on Extremal Problems of Edges in ${C_{2 t + 1}, C_{\geq l}}$ -Free Graphs

Lingting Fu, Jian Wang^*, Caiping Wu

College of Mathematics, Taiyuan University of Technology, Jinzhong Shanxi

Received: Jan. 26^th, 2023; accepted: Feb. 19^th, 2023; published: Feb. 28^th, 2023

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 \in F$ , G does not contain F as a subgraph, then we say G is $F$ -free. The Turán number $e x (n, F)$ is defined as the maximum number of edges in an $F$ -free graph on n vertices. Let $C_{2 t + 1}$ denote a cycle of length $2 t + 1$ , let $C_{\geq l}$ denote a family of cycles with lengths from $l$ to n and let $P_{l}$ denote a path of length $l$ . In the present paper, we study the Turán number for ${C_{2 t + 1}, C_{\geq l}}$ -free graphs and ${C_{2 t + 1}, P_{l}}$ -free graphs. For $l > 4 t - 2$ , we determine that $e x (n, {C_{2 t + 1}, C_{\geq l}}) = ⌊ \frac{l - 1}{2} ⌋ (n - ⌊ \frac{l - 1}{2} ⌋)$ . For $l$ is odd and $l \geq 4 t - 2$ , we prove that $e x (n, {C_{2 t + 1}, P_{l}}) = ⌊ \frac{l - 1}{2} ⌋ (n - ⌊ \frac{l - 1}{2} ⌋)$ .

Keywords:Turán Number, $F$ -Free Graph, Paths and Cycles

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

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

设 $G_{1}$ 和 $G_{2}$ 是图G的两个不相交的子图， $G_{1} \cup G_{2}$ 表示 $G_{1}$ 和 $G_{2}$ 的并图，其顶点集为 $V (G_{1}) \cup V (G_{2})$ ，边集为 $E (G) = E (G_{1}) \cup E (G_{2})$ 。 $G_{1} \lor G_{2}$ 表示 $G_{1}$ 和 $G_{2}$ 的联图，其顶点集为 $V (G_{1}) \cup V (G_{2})$ ，边集为 $E (G) = E (G_{1}) \cup E (G_{2}) \cup {x y | x \in V (G_{1}), y \in V (G_{2})}$ 。 $K_{n}$ 表示n个顶点的完全图， $E_{n}$ 表示n个顶点的空图。令 $T_{r} (n)$ 表示n个顶点的Turán图，即含有n个顶点的完全r部图且每个部集的大小为 $⌈ \frac{n}{r} ⌉$ 或 $⌊ \frac{n}{r} ⌋$ 。

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

定理1.1. 若G是n个顶点的 $K_{3}$ -禁止图，则

$e x (n, K_{3}) = ⌊ \frac{n^{2}}{4} ⌋ .$

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

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

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

$e x (n, K_{r + 1}) = e (T_{r} (n)) .$

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

定理1.3. 若 $n \geq l + 1$ ，则

$e x (n, P_{l}) = \frac{(l - 2) n}{2} .$

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

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

定理1.4. 令 $n = q (l - 1) + r$ ， $0 \leq r \leq l - 2$ ，且 $l \geq 2$ ，则

$e x (n, P_{l}) = q (\begin{matrix} l - 1 \\ 2 \end{matrix}) + (\begin{matrix} r \\ 2 \end{matrix}) .$

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

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

定理1.5. 对于 $n \geq l$ ，

$e x (n, C_{\geq l}) \leq \frac{(l - 1) (n - 1)}{2} .$

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

Woodall [15] 在1976年以及Kopylov [14] 在1977年独立地证明了 $e x (n, C_{\geq l})$ 的精确值。

定理1.6. 令 $n = q (l - 2) + r$ ， $1 \leq r \leq l - 2$ ，且 $l \geq 3$ ， $q \geq 1$ ，则

$e x (n, C_{\geq l}) = q (\begin{matrix} l - 1 \\ 2 \end{matrix}) + (\begin{matrix} r \\ 2 \end{matrix}) .$

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

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

$e x (n, C_{2 k + 1}) = {\begin{array}{l} (\begin{matrix} n \\ 2 \end{matrix}) & n \leq 2 k, \\ g (n, k) & 2 k + 1 \leq n \leq 4 k - 1 \\ ⌊ \frac{n^{2}}{4} ⌋ & n \geq 4 k - 2. \end{array},$

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

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

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

定理1.8. 对于 $n \geq l > 4 t - 2$ ，则

$e x (n, {C_{2 t + 1}, C_{\geq l}}) = ⌊ \frac{l - 1}{2} ⌋ (n - ⌊ \frac{l - 1}{2} ⌋) .$

注意到当 $n \leq l$ 时，根据定理1.7和1.8可以推出 $e x (n, {C_{2 t + 1}, C_{\geq l}}) = e x (n, C_{2 t + 1})$ 。显然， $E_{⌊ \frac{l - 1}{2} ⌋} \lor E_{n - ⌊ \frac{l - 1}{2} ⌋}$ 是一个 ${C_{2 t + 1}, C_{\geq l}}$ -禁止图，定理1.8证明了 $E_{⌊ \frac{l - 1}{2} ⌋} \lor E_{n - ⌊ \frac{l - 1}{2} ⌋}$ 是一个边数最多的 ${C_{2 t + 1}, C_{\geq l}}$ -禁止图。

定理1.9. 对于 $n \geq l \geq 4 t - 2$ ，则

$e x (n, {C_{2 t + 1}, P_{l}}) = ⌊ \frac{l - 1}{2} ⌋ (n - ⌊ \frac{l - 1}{2} ⌋) .$

注意到当 $n \leq l$ 时，根据定理1.7和1.9可以推出 $e x (n, {C_{2 t + 1}, P_{l}}) = e x (n, C_{2 t + 1})$ 。显然， $E_{⌊ \frac{l - 1}{2} ⌋} \lor E_{n - ⌊ \frac{l - 1}{2} ⌋}$ 是一个 ${C_{2 t + 1}, P_{l}}$ -禁止图，定理1.9证明了 $E_{⌊ \frac{l - 1}{2} ⌋} \lor E_{n - ⌊ \frac{l - 1}{2} ⌋}$ 是一个边数最多的 ${C_{2 t + 1}, P_{l}}$ -禁止图。

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

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

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

$N_{G} (X) = {v \in V (G) : \exists u \in X, u v \in E (G)}$

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

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

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

$c (G) \geq \min {2 δ (G), n} .$

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

2. 定理1.8的证明

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

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

情况1： $l = 2 k + 1$ 。

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

$e (G) \leq e x (2 k, C_{2 t + 1}) = k^{2} .$

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

若G不是连通的，不妨设 $G_{1}$ 是G的含有 $n_{1}$ 个顶点的连通分支，则由归纳假设可知

$\begin{matrix} e (G) = e (G_{1}) + e (G - V (G_{1})) \\ \leq ⌊ \frac{l - 1}{2} ⌋ (n_{1} - ⌊ \frac{l - 1}{2} ⌋) + ⌊ \frac{l - 1}{2} ⌋ (n - n_{1} - ⌊ \frac{l - 1}{2} ⌋) \\ \leq ⌊ \frac{l - 1}{2} ⌋ (n - ⌊ \frac{l - 1}{2} ⌋) . \end{matrix}$

若G不是二连通的，不妨设 $G_{1}$ 是G的含有 $n_{1}$ 个顶点的二连通分支，同样由归纳假设可知

$\begin{matrix} e (G) = e (G_{1}) + e (G - V (G_{1})) \\ \leq ⌊ \frac{l - 1}{2} ⌋ (n_{1} - ⌊ \frac{l - 1}{2} ⌋) + ⌊ \frac{l - 1}{2} ⌋ (n - n_{1} + 1 - ⌊ \frac{l - 1}{2} ⌋) \\ \leq ⌊ \frac{l - 1}{2} ⌋ (n - ⌊ \frac{l - 1}{2} ⌋) . \end{matrix}$

若G是二连通的，当 $n \geq 2 k + 1$ 时，若存在一个点v，使得 $\deg (v) \leq k$ ，则

$e (G) = e (G - v) + \deg (v) \leq k (n - 1 - k) + k = k (n - k) = ⌊ \frac{l - 1}{2} ⌋ (n - ⌊ \frac{l - 1}{2} ⌋) .$

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

情况2： $l = 2 k$ 。

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

$e (G) \leq e x (2 k - 1, C_{2 t + 1}) = k (k - 1) .$

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

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

$e (G) = ⌊ \frac{l - 1}{2} ⌋ (n - ⌊ \frac{l - 1}{2} ⌋) .$

若G是二连通的，当 $n \geq 2 k$ 时，若存在一个点v，使得 $\deg (v) \leq k - 1$ ，则

$\begin{matrix} e (G) = e (G - v) + \deg (v) \\ \leq (k - 1) (n - 1 - k + 1) + k - 1 \\ = (k - 1) (n - k + 1) \\ = ⌊ \frac{l - 1}{2} ⌋ (n - ⌊ \frac{l - 1}{2} ⌋) . \end{matrix}$

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

的圈，矛盾。

3. 定理1.9的证明

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

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

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

$e (G) \leq e x (2 k, C_{2 t + 1}) = k^{2} .$

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

若G不是连通的，不妨设 $G_{1}$ 是G的含有 $n_{1}$ 个顶点的连通分支，则由归纳假设可知

若G不是二连通的，不妨设 $G_{1}$ 是G的含有 $n_{1}$ 个顶点的二连通分支，同样由归纳假设可知

若G是二连通的，当 $n \geq 2 k + 2$ 时，若存在一个点v，使得 $\deg (v) \leq k$ ，则

$e (G) = e (G - v) + \deg (v) \leq k (n - 1 - k) + k = k (n - k) = ⌊ \frac{l - 1}{2} ⌋ (n - ⌊ \frac{l - 1}{2} ⌋) .$

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

4. 结论

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

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

文章引用

傅凌婷,王健,武彩萍. {C_2t+1,C≥l}-禁止图的边极值问题研究
Research on Extremal Problems of Edges in {C_2t+1,C≥l}-Free Graphs[J]. 应用数学进展, 2023, 12(02): 764-770. https://doi.org/10.12677/AAM.2023.122078

参考文献

1. Alon, N., Krivelevich, M. and Sudakov, B. (2003) Turán Numbers of Bipartite Graphs and Related Ramsey-Type Ques-tions. Combinatorics, Probability and Computing, 12, 477-494. https://doi.org/10.1017/S0963548303005741

2. Alon, N. and Shikhelman, C. (2016) Many T Copies in H-Free Graphs. Journal of Combinatorial Theory, Series B, 121, 146-172. https://doi.org/10.1016/j.jctb.2016.03.004

3. Erdős, P. and Gallai, T. (1959) On Maximal Paths and Circuits of Graphs. Acta Mathematica Hungarica, 10, 337-356. https://doi.org/10.1007/BF02024498

4. Füredi, Z. (1991) On a Turán type problem of Erdős. Combinatorica, 11, 75-79. https://doi.org/10.1007/BF01375476

5. Keevash, P. (2011) Hypergraph Turan Problems. Surveys in Combinatorics, 392, 83-140. https://doi.org/10.1017/CBO9781139004114.004

6. Kővári, P., Sós, V. and Turán, P. (1954) On a Problem of Zarankiewicz. In: Colloquium Mathematicum, Vol. 3, Polska Akademia Nauk, Warszawa, 50-57.

7. Mantel, W. (1907) Promblem 28. Wiskundige Opgaven, 10, 60-61.

8. Sidorenko, A. (1995) What We Know and What We Do Not Know about Turán Numbers. Graphs and Combinatorics, 11, 179-199. https://doi.org/10.1007/BF01929486

9. Turán, P. (1941) On an Extremal Problem in Graph Theory. Mathematica Fiz. Lapok, 48, 436-452.

10. Yuan, L.T. (2018) Ex-tremal Graphs for the k-Flower. Journal of Graph Theory, 89, 26-39. https://doi.org/10.1002/jgt.22237

11. Yuan, L.T. (2021) Extremal Graphs for Odd Wheels. Journal of Graph Theory, 98, 691-707. https://doi.org/10.1002/jgt.22727

12. Yuan, L.T. (2022) Extremal Graphs for Edge Blow-Up of Graphs. Journal of Combinatorial Theory, Series B, 152, 379-398. https://doi.org/10.1016/j.jctb.2021.10.006

13. Faudree, R.J. and Schelp, R.H. (1975) Path Ramsey Numbers in Multicolorings. Journal of Combinatorial Theory, Series B, 19, 150-160. https://doi.org/10.1016/0095-8956(75)90080-5

14. Kopylov, G.N. (1977) Maximal Paths and Cycles in a Graph. Doklady Akademii Nauk SSSR, 234, 19-21.

15. Woodall, D.R. (1976) Maximal Circuits of Graphs I. Acta Mathematica Hungarica, 28, 77-80. https://doi.org/10.1007/BF01902497

16. Füredi, Z. and Gunderson D.S. (2015) Extremal Numbers for Odd Cy-cles. Combinatorics, Probability and Computing, 24, 641-645. https://doi.org/10.1017/S0963548314000601

17. Dirac, G.A. (1952) Some Theorems on Abstract Graphs. Pro-ceedings of the London Mathematical Society, s3-2, 69-81. https://doi.org/10.1112/plms/s3-2.1.69

NOTES

^*通讯作者。

期刊菜单