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

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

傅凌婷,王健*,武彩萍

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

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

摘要

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

关键词

图兰数, F -禁止图,路和圈

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

Lingting Fu, Jian Wang*, Caiping Wu

College of Mathematics, Taiyuan University of Technology, Jinzhong Shanxi

Received: Jan. 26th, 2023; accepted: Feb. 19th, 2023; published: Feb. 28th, 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 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 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 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 l } ) = l 1 2 ( n l 1 2 ) . For l is odd and l 4 t 2 , we prove that e x ( n , { C 2 t + 1 , P l } ) = l 1 2 ( n l 1 2 ) .

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

Copyright © 2023 by author(s) and Hans Publishers Inc.

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 ) V ( G ) E ( H ) E ( G ) ,则称H是G的一个子图。令 F 表示由一些图组成的集族,如果对任意的 F 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 G 2 表示 G 1 G 2 的并图,其顶点集为 V ( G 1 ) V ( G 2 ) ,边集为 E ( G ) = E ( G 1 ) E ( G 2 ) G 1 G 2 表示 G 1 G 2 的联图,其顶点集为 V ( G 1 ) V ( G 2 ) ,边集为 E ( G ) = E ( G 1 ) E ( G 2 ) { x y | x V ( G 1 ) , y V ( G 2 ) } K n 表示n个顶点的完全图, E n 表示n个顶点的空图。令 T r ( n ) 表示n个顶点的Turán图,即含有n个顶点的完全r部图且每个部集的大小为 n r n r

1907年,Mantel [7] 证明了以下定理:

定理1.1. 若G是n个顶点的 K 3 -禁止图,则

e x ( n , K 3 ) = n 2 4 .

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

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

定理1.2.对于 n r + 1 r 2

e x ( n , K r + 1 ) = e ( T r ( n ) ) .

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

定理1.3. 若 n l + 1 ,则

e x ( n , P l ) = ( l 2 ) n 2 .

l 1 整除n时, 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 r l 2 ,且 l 2 ,则

e x ( n , P l ) = q ( l 1 2 ) + ( r 2 ) .

相应的极图为 q K l 1 K r ,即q个点不交的 K l 1 和一个 K r 的并。当 l 是偶数且同时r是 l 2 或者 l 2 1 ,极图为 t ( 0 t < q ) 个点不交的 K l 1 和一个H的并,其中H为 K l 2 1 K n t ( l 1 ) l 2 + 1

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

定理1.5. 对于 n l

e x ( n , C l ) ( l 1 ) ( n 1 ) 2 .

l 2 整除 n 1 时, n 1 l 2 K l 1 共用一个点的图是取到等号的一个图。

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

定理1.6. 令 n = q ( l 2 ) + r 1 r l 2 ,且 l 3 q 1 ,则

e x ( n , C l ) = q ( l 1 2 ) + ( r 2 ) .

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

定理1.7. 对 n 1 2 k + 1 5

e x ( n , C 2 k + 1 ) = { ( n 2 ) n 2 k , g ( n , k ) 2 k + 1 n 4 k 1 n 2 4 n 4 k 2. ,

其中,当 n = ( s 1 ) ( 2 k 1 ) + r ,且 s 1 2 r 2 k ,s和r都是整数时,

g ( n , k ) = ( s 1 ) ( 2 k 2 ) + ( r 2 ) .

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

定理1.8. 对于 n l > 4 t 2 ,则

e x ( n , { C 2 t + 1 , C l } ) = l 1 2 ( n l 1 2 ) .

注意到当 n l 时,根据定理1.7和1.8可以推出 e x ( n , { C 2 t + 1 , C l } ) = e x ( n , C 2 t + 1 ) 。显然, E l 1 2 E n l 1 2 是一个 { C 2 t + 1 , C l } -禁止图,定理1.8证明了 E l 1 2 E n l 1 2 是一个边数最多的 { C 2 t + 1 , C l } -禁止图。

定理1.9. 对于 n l 4 t 2 ,则

e x ( n , { C 2 t + 1 , P l } ) = l 1 2 ( n l 1 2 ) .

注意到当 n l 时,根据定理1.7和1.9可以推出 e x ( n , { C 2 t + 1 , P l } ) = e x ( n , C 2 t + 1 ) 。显然, E l 1 2 E n l 1 2 是一个 { C 2 t + 1 , P l } -禁止图,定理1.9证明了 E l 1 2 E n l 1 2 是一个边数最多的 { C 2 t + 1 , P l } -禁止图。

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

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

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

N G ( X ) = { v V ( G ) : u X , u v 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 ) min { 2 δ ( G ) , n } .

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

2. 定理1.8的证明

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

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

情况1: l = 2 k + 1

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

e ( G ) e x ( 2 k , C 2 t + 1 ) = k 2 .

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

若G不是连通的,不妨设 G 1 是G的含有 n 1 个顶点的连通分支,则由归纳假设可知

e ( G ) = e ( G 1 ) + e ( G V ( G 1 ) ) l 1 2 ( n 1 l 1 2 ) + l 1 2 ( n n 1 l 1 2 ) l 1 2 ( n l 1 2 ) .

若G不是二连通的,不妨设 G 1 是G的含有 n 1 个顶点的二连通分支,同样由归纳假设可知

e ( G ) = e ( G 1 ) + e ( G V ( G 1 ) ) l 1 2 ( n 1 l 1 2 ) + l 1 2 ( n n 1 + 1 l 1 2 ) l 1 2 ( n l 1 2 ) .

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

e ( G ) = e ( G v ) + deg ( v ) k ( n 1 k ) + k = k ( n k ) = l 1 2 ( n l 1 2 ) .

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

情况2: l = 2 k

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

e ( G ) e x ( 2 k 1 , C 2 t + 1 ) = k ( k 1 ) .

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

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

e ( G ) = l 1 2 ( n l 1 2 ) .

若G是二连通的,当 n 2 k 时,若存在一个点v,使得 deg ( v ) k 1 ,则

e ( G ) = e ( G v ) + deg ( v ) ( k 1 ) ( n 1 k + 1 ) + k 1 = ( k 1 ) ( n k + 1 ) = l 1 2 ( n l 1 2 ) .

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

的圈,矛盾。

3. 定理1.9的证明

类似于定理1.8的证明,我们利用数学归纳法来对 l 为奇数时的 { C 2 t + 1 , P l } -禁止图 ( l 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 4 t 2 ,根据定理1.7可得

e ( G ) e x ( 2 k , C 2 t + 1 ) = k 2 .

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

若G不是连通的,不妨设 G 1 是G的含有 n 1 个顶点的连通分支,则由归纳假设可知

e ( G ) = e ( G 1 ) + e ( G V ( G 1 ) ) l 1 2 ( n 1 l 1 2 ) + l 1 2 ( n n 1 l 1 2 ) l 1 2 ( n l 1 2 ) .

若G不是二连通的,不妨设 G 1 是G的含有 n 1 个顶点的二连通分支,同样由归纳假设可知

e ( G ) = e ( G 1 ) + e ( G V ( G 1 ) ) l 1 2 ( n 1 l 1 2 ) + l 1 2 ( n n 1 + 1 l 1 2 ) l 1 2 ( n l 1 2 ) .

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

e ( G ) = e ( G v ) + deg ( v ) k ( n 1 k ) + k = k ( n k ) = l 1 2 ( n l 1 2 ) .

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

4. 结论

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

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

文章引用

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

参考文献

  1. 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. 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. 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. 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. 5. Keevash, P. (2011) Hypergraph Turan Problems. Surveys in Combinatorics, 392, 83-140. https://doi.org/10.1017/CBO9781139004114.004

  6. 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. 7. Mantel, W. (1907) Promblem 28. Wiskundige Opgaven, 10, 60-61.

  8. 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. 9. Turán, P. (1941) On an Extremal Problem in Graph Theory. Mathematica Fiz. Lapok, 48, 436-452.

  10. 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. 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. 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. 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. 14. Kopylov, G.N. (1977) Maximal Paths and Cycles in a Graph. Doklady Akademii Nauk SSSR, 234, 19-21.

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

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

  18. NOTES

    *通讯作者。

期刊菜单