An implicit degree condition for relative length of long paths and cycles in graphs |
| |
Authors: | Email author" target="_blank">Jun-qing?CaiEmail author Hao?Li |
| |
Institution: | 1.School of Management,Qufu Normal University,Rizhao,China;2.L.R.I, UMR 8623,CNRS and Université Paris-Sud 11,Orsay,France;3.Institute for Interdisciplinary Research,Jianghan University,Wuhan,China |
| |
Abstract: | For a graph G, we denote by p(G) and c(G) the number of vertices of a longest path and a longest cycle in G, respectively. For a vertex v in G, id(v) denotes the implicit degree of v. In this paper, we obtain that if G is a 2-connected graph on n vertices such that the implicit degree sum of any three independent vertices is at least n + 1, then either G contains a hamiltonian path, or c(G) ≥ p(G) ? 1. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|