首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Longest cycles in 4-connected graphs
Authors:Junqing Cai  Hao Li  Qiang Sun
Institution:1. School of Management, Qufu Normal University, Rizhao, PR China;2. LRI, UMR 6823 CNRS and Université Paris-Saclay, B.650, Orsay Cedex, France;3. Institute for Interdisciplinary Research, Jianghan University, Wuhan, PR China;4. School of Mathematical Science, Yangzhou University, Yangzhou, PR China
Abstract:Let σ41=min{i=14d(vi)+|?i=14N(vi)|?|?i=14N(vi)|:{v1,v2,v3,v4} is an independent set of a graph G}. In this paper, we give a low bound for the length of a longest cycle in a 4-connected graph and get the following result: If G is a 4-connected graph on n vertices, then the circumference c(G)min{n,σ412}. Moreover, we give graphs to show that the connectivity in our result is best possible with respect to the low bound and the low bound in our result is also best possible with respect to the connectivity.
Keywords:Circumference  Non-insertible vertex  Independent set
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号