Large cycles in 4-connected graphs

详细信息    查看全文

• 作者：M.Zh. Nikoghosyan ; Zh.G. Nikoghosyan
• 关键词：Hamilton cycle ; Dominating cycle ; Longest cycle ; Minimum degree ; Connectivity
• 刊名：Discrete Mathematics
• 出版年：2011
• 出版时间：28 February 2011
• 年：2011
• 卷：311
• 期：4
• 页码：302-306
• 全文大小：195 K

文摘

The first result states that every 4-connected graph G with minimum degree δ and connectivity κ either contains a cycle of length at least 4δ−κ−4 or every longest cycle in G is a dominating cycle. The second result states that any such graph under the additional condition δ≥α either contains a cycle of length at least 4δ−κ−4 or is hamiltonian, where α denotes the independence number of G. Both results are sharp in all respects.