Large cycles in 4-connected graphs |
| |
Authors: | MZh Nikoghosyan ZhG Nikoghosyan |
| |
Institution: | aInstitute for Informatics and Automation Problems, National Academy of Sciences, P. Sevak 1, Yerevan 0014, Armenia |
| |
Abstract: | 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. |
| |
Keywords: | Hamilton cycle Dominating cycle Longest cycle Minimum degree Connectivity |
本文献已被 ScienceDirect 等数据库收录! |