On arithmetic progressions of cycle lengths in graphs
更新时间:2023-05-07 10:46:01 阅读量: 实用文档 文档下载
- on是开还是关推荐度:
- 相关推荐
On Arithmetic Progressions of Cycle Lengths in
Graphs
Jacques Verstra¨e te
Department of Pure Mathematics and Mathematical Statistics
Centre for Mathematical Sciences
Wilberforce Road,Cambridge CB3OWB
England August1999.
jbav@185fc662ddccda38376baf7a
Abstract
A recently posed question of H¨a ggkvist and Scott’s asked whether
or not there exists a constant c such that if G is a graph of minimum
degree ck then G contains cycles of k consecutive even lengths.In
this paper we answer the question by proving that for k≥2,a
bipartite graph of average degree at least4k and girth g contains
cycles of(g/2?1)k consecutive even lengths.We also obtain a
short proof of the theorem of Bondy and Simonovits,that a graph
of order n and size at least8(k?1)n1+1/k has a cycle of length2k.
Erd?o s and Burr[4]conjectured that for every odd number k,there is a constant c k such that for every natural number m,every graph of average degree at least c k contains a cycle of length m modulo k.Erd?o s and Burr[4] settled their conjecture in the case m=2and Robertson(see[4])settled the case m=0.The full conjecture was resolved by Bollob′a s[1],who proved the conjecture with c k=2[(k+1)k?1]/k.In this paper,we show that c k=8k will do.Thomassen[11]later showed cycles of all even lengths modulo k are obtained under the hypothesis that the average degree is at least4k(k+1),without requiring k to be odd.Thomassen[10]also proved that if G is a graph of minimum degree at least three and girth at least 2(k2+1)(3·2k2+1+(k2+1)2?1),then G contains cycles of all even lengths modulo k.
1
Bondy and Vince[3]proved that in a graph in which all but at most two vertices have degree at least three,there exist two cycles whose lengths di?er by at most two.This answered a conjecture of Erd?o s and was also studied by H¨a ggkvist and Scott[8].Recently,H¨a ggkvist and Scott[7], considered extending this to considering arithmetic progressions of cycle lengths in graphs.H¨a ggkvist and Scott[7]proved that if G is a graph of minimum degree at least300k2then G contains k+1consecutive even cycle lengths.The same authors asked if a linear bound on the minimum degree is possible.In this paper,we answer the question of H¨a ggkvist and Scott in the following theorem.
Theorem1Let k≥2be a natural number and G a bipartite graph of average degree at least4k and girth g.Then there exist cycles of(g/2?1)k consecutive even lengths in G.Moreover,the shortest of these cycles has length at most twice the radius of G.
This result generalises the above-mentioned result of Bollob′a s and partly generalises that of Thomassen,insofar as Thomassen’s result is valid for graphs of minimum degree at least three,whereas the result above requires average degree at least eight.The graph K k,n?k shows that we require the average degree to be at least about2k to ensure the conclusion of Theorem 1.
The following lemma lies at the heart of the proof of Theorem1.It was originally inspired by methods used by Gy′a rf′a s,Koml′o s and Szemer′e di[6]. Whilst this paper was being written,the lemma was discovered to be implicit in a lemma of Bondy and Simonovits[2].Nevertheless,the proof is short and is retained here for completeness.
Lemma2Let H be a graph comprising a cycle with a chord.Let(A,B) be a non-trivial partition of V(H).Then H contains A–B paths of every length less than|H|,unless H is bipartite with bipartition(A,B).
185fc662ddccda38376baf7abel the vertices of the cycle0,1,...,n?1where n=|H|. Suppose H does not contain A–B paths of every length less than n,and let
2
m be the smallest integer for which there is no A–B path of length m not using the chord;m>1since(A,B)is a non-trivial partition of V(H).We remark also that m≤n/2,or H would contain A–B paths of all lengths less than n.
Nowχ(j)=χ(j+m)for every j∈V(H),whereχis the characteristic function of A(label arithmetic is modulo n).Let d=hcf(n,m).Then there are integers p and q such that pm+qn=d;henceχ(j)=χ(j+d)for every j.But then there is no A–B path of length d round the cycle;thus d=m and m|n.In particular,A–B paths of every length less than m exist by the de?nition of m,so A–B paths of every length other than multiples of m exist by periodicity ofχ.
We?nd paths of the remaining lengths km,1≤k≤n/m?1,using the chord.Suppose?rst that the chord joins two vertices within distance m on the cycle,say0and r where1 So we may suppose the chord is0r,where m Thus it follows,asχ(j)=χ(m+j),that for?m 3 We conclude,therefore,that |H |is even and the vertices of the cycle are alternately in A and in B .It is immediately seen that,under these circumstances,if the chord joins two vertices in the same class then H contains A –B paths of all lengths less than |H |.Consequently,the chord joins A to B ,so H is bipartite,with bipartition (A,B ). Lemma 3Let k ≥2be a natural number and let G be a graph of average degree at least 2k and girth g .Then G contains a cycle of length at least (g ?2)k +2,with at least one chord. Proof.It is easily seen that a graph G of average degree at least 2k contains a subgraph H of minimum degree at least k +1.If P is a longest path in H ,then an endvertex v of P has all its neighbours on P .Some neighbour u of v is at distance at least (g ?2)k +1from v on P .Hence P +uv is a cycle of length at least (g ?2)k +2.As k +1≥3,this cycle has at least one chord. Proof of Theorem 1.We may assume that G is connected and let the radius of G be rad(G ).Choose a central vertex v 0∈V (G ),and let V i denote the set of vertices a distance i from v 0in G .Then there exists l such that V l ∪V l +1spans a graph G with at least k |V l ∪V l +1|edges.By Lemma 3,?nd H ?G comprising a cycle,of length at least (g ?2)k +2,with a chord.Let T be a minimal subtree of T ,restricted to i ≤l V i ,such that T contains V (H )∩V l .The minimality of T ensures that it branches at its root.Now let A be the set of vertices of H in one of these branches and let B =V (H )\A .By Lemma 2,and as (A,B )is not the bipartition of H ,there are A –B paths of all lengths up to (g ?2)k +1,all disjoint from T ?end(T ).Each A –B path of even length s ,together with a subpath of T between the ends of such a path,gives rise to a cycle of length s +2r ,where r is the distance from V l to the root of T .Note that,as G is bipartite,all paths of even length with one end in A have their other end in V l .This gives cycles C 2r +2,C 2r +4,..,C 2r +(g ?2)k ,of (g/2?1)k consecutive even lengths,and since v 0is a central vertex,2r +2≤rad(G ),as required. 4 We de?ne the even girth of a graph G to be the length of a shortest even cycle in G.Theorem1easily extends to general graphs,as is shown by the following corollary. Corollary4Let k≥2be a natural number,and let G be a graph of average degree at least8k and even girth g.Then there are cycles of(g/2?1)k consecutive even lengths in G. Proof.This follows from the observation that a graph of average degree at least8k has a spanning bipartite subgraph of average degree at least4k, and then applying Theorem1to this bipartite subgraph. In the case of graphs of average degree at least6k,we may also argue as follows.Given a vertex v0,let V l denote the vertices a distance l from v0.Then either there exists l such that V l∪V l+1spans a bipartite graph of average degree at least2k,or there exists l such that V l spans a graph of average degree at least2k.In the former case,the method of Theorem1gives cycles of all even lengths in an integer interval of form[2r+1,2r+(g?2)k+1] and the latter case gives(also following the proof of Theorem1)cycles of all odd lengths in an integer interval of form[2r+1,2r+(g?2)k+1].So we have the following theorem: Theorem5Let k≥2be a natural number,and let G be a graph of average degree at least6k and girth g.Then,for some odd number r≥3,there exist cycles of all even lengths or all odd lengths in the interval[r,r+(g?2)k]. The above result recalls the result of Bondy and Vince[3],that if G is a graph with at most two vertices of degree at most two,then G contains cycles of two consecutive lengths or two consecutive even lengths.This was proved using a technique of Thomassen and Toft[12].In comparison,note that Theorem5requires average degree at least6k where k≥2.Therefore, to ensure two cycles of consecutive lengths or consecutive even lengths,we require average degree at least twelve,which is higher than what is required in the context of Bondy and Vince’s results. The following result is proved in the same was as Theorem1: 5 Corollary6Let k≥2be a natural number,and suppose that G has chro-matic number at least2k+2and girth at least g.Then G contains cycles of k(g?2)consecutive lengths. The idea is that some level of a breadth-?rst search tree induces a graph of chromatic number at least k+1.Such a graph contains an odd cycle of length at least k(g?2)+1with a chord.We then apply the colouring lemma to deduce that G contains cycles of k(g?2)consecutive lengths. In a sense,this generalizes a result of Gy′a rf′a s who showed that if G has chromatic number at least2k+2,then G contains cycles of k distinct odd lengths.These ideas may also be used to give a relatively short proof that r(C2k+1,K n) n1+1/(k+1).However,better results are easily obtain—for example,it is possible to show that r(C2k+1,K n) n1+1/(k+1)(log2n)?1/k. The cycles we have obtained are all very close together in the sense that they share many vertices.H¨a ggkvist and Scott[7]asked if it was possible, under an appropriate bound on the size of the graph,to?nd disjoint cycles of k consecutive even lengths.This question also remains open,noting that a bound of order at least k2on the average degree would be required for disjoint cycles of k consecutive even lengths.This is shown,for example,by K l,n?l where l<2k+k(k?1)/2and n is su?ciently large. We remark that from Theorem1we may obtain a result on extremal numbers for even cycles,that slightly improves the result obtained by Bondy and Simonovits[2](see Corollary9).From their paper,it follows that a graph of order n and size at least90kn1+1/k contains a cycle of length2k. Two simple lemmas are required before proving our result.The?rst lemma is a special case of a lemma of Kostochka and Pyber[9]. Lemma7Let G be a graph of order n and size at least cn1+1/k,where c≥1.Then G contains a subgraph of average degree at least c and radius at most k. Proof.We may assume that G has minimum degree at least cn1/k.Let v0 be an arbitrary vertex in G and de?ne H i to be the subgraph of G induced by 6 vertices at distance at most i from v0.De?ne r=min{i:e(H i)≥1 c|H i|}. 2 cn1/k|H i?1|for all i and so,by de?nition of r,|H r?1|> Clearly e(H i)≥1 2 n1/k|H r?2|which gives|H r?1|>n(r?1)/k.Since|H r?1|≤n,r?1 r is the desired subgraph. Lemma8Let G be a graph of order n with e(G)≥2n1+1/k where k≥2. Then G has girth at most2k+1. Proof.By Lemma6,G has a subgraph H of radius at most k and average degree at least two.So H contains a cycle and some cycle in H has length at most2k+1. In particular,if G is bipartite and k=2in Lemma7,then G has a cycle of length four.For comparison,a standard result states that a graph which has at least n3/2/2+n/4edges contains a cycle of length four.We are able, using Theorem1,to show the existence of longer even cycles: Theorem9Let G be a bipartite graph of order n and girth g,and of size at least4 2(k?1)/(g?2) n1+1/k,where k≥2is an integer.Then G has a cycle of length2k. Proof.By Lemma7,either G contains a cycle of length2k or g<2k and k≥3.In the latter case, 2(k?1)/(g?2) ≥2.Lemma6shows that G contains a subgraph of average degree at least4 2(k?1)/(g?2) and of radius at most k.By Theorem1,there are cycles of at least k?1 consecutive even lengths in H,the shortest length being at most2k.So one of these cycles must have length exactly2k. As a corollary to Theorem8,we slightly improve the result of Bondy and Simonovits[2]: Corollary10Let G be a graph of order n and size at least8(k?1)n1+1/k, where k≥2.Then G contains a cycle of length2k. Acknowledgements I would like to thank Andrew Thomason for his many helpful suggestions. 7 References [1]Bollob′a s,B.,Cycles Modulo k,Bull.London Math.Soc.9(1977)97–98. [2]Bondy,J.,Simonovits,M.,Cycles of Even Length in Graphs,185fc662ddccda38376baf7a- binatorial Theory B16(1974)97–105. [3]Bondy,J.,Vince,A.Cycles in a graph whose lengths di?er by one or two,J.Graph Theory27(1998)11–15. [4]Erd?o s,P.,Some recent problems and results in graph theory,combi- natorics,and number theory,Proc.Seventh S–E 185fc662ddccda38376baf7abinatorics, Graph Theory and Computing,Utilitas Math.,Winnipeg,(1976)3–14. [5]Erd?o s,P.,Some of my recent problems in Combinatorial Number The- ory,Geometry and Combinatorics in:Graph Theory,Combinatorics and Algorithms,Volume1,Proc.Seventh Quadrennial International Conference on the Theory and Applications of Graphs,Y.Alavi and A. Schwenk eds.,John Wiley and Sons(1995)335–349. [6]Gy′a rf′a s,A.,Koml′o s,J.,Szemer′e di,E.,On the distribution of cycle lengths in graphs,J.Graph Theory8(1984)441–466. [7]H¨a ggkvist,R.,Scott,A.,Arithmetic progressions of cycles,preprint. [8]H¨a ggkvist,R.,Scott,A.,Cycles of nearly equal length in cubic graphs, preprint. [9]Kostochka,A.,Pyber,L.,Small topological complete subgraphs of dense graphs,Combinatorica8(1)(1988)83-86. [10]Thomassen,C.,Girth in Graphs,185fc662ddccda38376baf7abinatorial Theory B35(1983) 129–141. [11]Thomassen,C.,Paths,Circuits and Subdivisions in:Selected Topics in Graph Theory3,L.Beineke,R.Wilson eds.,Academic Press(1988) 97–133. 8 [12]Thomassen,C.,Toft,B.,Non-separating induced cycles in graphs,J. Combinatorial Theory B31(1981)199–224. 9
正在阅读:
On arithmetic progressions of cycle lengths in graphs05-07
企业财务风险控制问题及其研究【毕业论文,绝对精品】05-30
群体性食物中毒演练方案09-30
2022年上海对外经贸大学马克思主义学院822马克思主义基本原理考04-05
材料的介电常数和磁导率的测量02-29
护理人员的 - 时间管理课件范文01-07
劝爸爸戒烟作文600字06-30
IC 燃气表说明书09-17
2016起重机械作业桥门式起重机司机复习题500题 - 3057511-27
临床生化室内质量控制SOP文件04-07
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- progressions
- arithmetic
- lengths
- graphs
- cycle
- 交流接触器作用和工作原理
- 电工实训报告精选范文
- 2013年考研英语必备之新东方考研英语词汇+词根联想记忆法打印版(完整版)
- 六年级上册期末测试英语试卷(含听力)及答案-人教PEP版
- 桂林游记作文800字初二
- 【真题】2017年孝感市中考英语试卷含答案解析(Word版)
- 【冲刺卷】中考九年级历史下第二单元第二次工业革命和近代科学文化模拟试题带答案
- 2012年天津市建设工程预算基价定额说明
- 窗口单位专项整治工作总结
- 患者评估、再评估制度
- 安徽省淮北市2017届高三上学期第一次模拟考试
- 三国演义回检测及答案
- 信息管理中数据库技术的应用-信息管理论文-管理论文
- 文明单位创建问卷调查
- 小学三年级下册心理健康教育教案(0001)
- 2020年广东省人口与计划生育条例
- 中秋国庆双节活动策划方案2020
- 高中英语必修一Unit2整体课件 教学设计方案.
- 雅思写作Work and careers类话题
- 香桥公园讲解员培训方案