Circumferences of regular claw-free graphs

详细信息    查看全文

• 作者：MingChu Li
• 关键词：Circumference ; Longest cycle ; Claw-free graph ; Regularity ; 3-connectedness
• 刊名：Discrete Mathematics
• 出版年：2006
• 出版时间：6 November 2006
• 年：2006
• 卷：306
• 期：21
• 页码：2682-2694
• 全文大小：287 K

文摘

A known result obtained independently by Fan and Jung is that every 3-connected k-regular graph on n vertices contains a cycle of length at least black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-C&_mathId=mml1&_user=10&_cdi=5632&_rdoc=7&_handle=V-WA-A-W-WV-MsSAYVA-UUA-U-AAZCWAYYYY-AAZWDEEZYY-VWUDVCVY-WV-U&_acct=C000050221&_version=1&_userid=10&md5=f738851b0e5b148a75f3c17b1bae8482"" title=""Click to view the MathML source"">min{3k,n}. This raises the question of how much can be said about the circumferences of 3-connected k-regular claw-free graphs. In this paper, we show that every 3-connected k-regular claw-free graph on n vertices contains a cycle of length at least black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-C&_mathId=mml2&_user=10&_cdi=5632&_rdoc=7&_handle=V-WA-A-W-WV-MsSAYVA-UUA-U-AAZCWAYYYY-AAZWDEEZYY-VWUDVCVY-WV-U&_acct=C000050221&_version=1&_userid=10&md5=b0fa0272449e12f4930fa386a4273b3d"" title=""Click to view the MathML source"">min{6k-17,n}.