The Lower and Upper Bounds of Turán Number for Odd Wheels

被引:0
作者
Byeong Moon Kim
Byung Chul Song
Woonjae Hwang
机构
[1] Gangneung-Wonju National University,Department of Mathematics
[2] Korea University,Division of Applied Mathematical Sciences
来源
Graphs and Combinatorics | 2021年 / 37卷
关键词
Turán number; Extremal graph; Odd wheel; 05C35; 05C55;
D O I
暂无
中图分类号
学科分类号
摘要
The Turán number for a graph H, denoted by ex(n,H)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {ex}(n,H)$$\end{document}, is the maximum number of edges in any simple graph with n vertices which doesn’t contain H as a subgraph. In this paper we find the lower and upper bounds for ex(n,W2t+1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text { ex}(n,W_{2t+1})$$\end{document}. We show that if n≥4t\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n\ge 4t$$\end{document}, then ex(n,W2t+1)≥⌊2n+t4⌋(n+t-12-⌊2n+t4⌋)+1.\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text { ex}(n,W_{2t+1})\ge \left\lfloor \lfloor \frac{2n+t}{4}\rfloor (n+\frac{t-1}{2}-\lfloor \frac{2n+t}{4}\rfloor )\right\rfloor +1.$$\end{document} We also show that for sufficiently large n and t≥5\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t\ge 5$$\end{document}, ex(n,W2t+1)≤n24+t-12n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text { ex}(n,W_{2t+1})\le \frac{ n^2 }{4}+{t-1\over 2}n$$\end{document}. Moreover we find the exact value of the Turán number for W9\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$W_9$$\end{document}. That is, we show that for sufficiently large n, ex(n,W9)=⌊n24⌋+⌈34n⌉+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text { ex}(n,W_9)= \lfloor \frac{n^2}{4}\rfloor +\lceil \frac{3}{4}n\rceil +1$$\end{document}.
引用
收藏
页码:919 / 932
页数:13
相关论文
共 16 条
[1]  
Bielak H(2014)The Turán number of the graph Ann. Univ. Mariae Curie SkLodowska Sect. A 68 21-29
[2]  
Kieliszek S(2016)The Turán number of the graph Discuss. Math. Graph Theory 36 683-694
[3]  
Bielak H(2011)Turán numbers of multiple paths and equibipartite forests Combin. Probab. Comput. 20 837-853
[4]  
Kieliszek S(2013)A note on Turán numbers for even wheels Graphs Combin. 29 1305-1309
[5]  
Bushaw N(2018)Turán numbers for odd wheels Discrete Math. 341 1150-1154
[6]  
Kettle N(1982)Compactness results in extremal graph theory Combinatorica 2 275-288
[7]  
Dzido T(2011)Turán numbers for disjoint copies of graphs Graphs Combin. 27 661-667
[8]  
Dzido T(2012)A note on the Turán function of even cycles Proc. Am. Math. Soc. 140 3687-3692
[9]  
Jastrzȩbski A(1941)On an extremal problem in graph theory (in Hungarian) Mat. Fiz. Lapok 48 436-452
[10]  
Erdös P(2017)The Turán number of disjoint copies Discrete Math. 340 132-139