Long cycles in graphs without hamiltonian paths |
| |
Authors: | Ken-ichi Kawarabayashi |
| |
Affiliation: | a National Institute of Informatics, 2-1-2, Hitotsubashi, Chiyoda-ku, Tokyo, Japan b Department of Mathematics, Keio University, 3-14-1, Hiyoshi, Kohoku-ku,Yokohama, Japan c Department of Mathematics, Asahi University, 1851, Hozumi, Gifu, Japan |
| |
Abstract: | ![]() For a graph G, p(G) and c(G) denote the order of a longest path and a longest cycle of G, respectively. Bondy and Locke [J.A. Bondy, S.C. Locke, Relative length of paths and cycles in 3-connected graphs, Discrete Math. 33 (1981) 111-122] consider the gap between p(G) and c(G) in 3-connected graphs G. Starting with this result, there are many results appeared in this context, see [H. Enomoto, J. van den Heuvel, A. Kaneko, A. Saito, Relative length of long paths and cycles in graphs with large degree sums, J. Graph Theory 20 (1995) 213-225; M. Lu, H. Liu, F. Tian, Relative length of longest paths and cycles in graphs, Graphs Combin. 23 (2007) 433-443; K. Ozeki, M. Tsugaki, T. Yamashita, On relative length of longest paths and cycles, preprint; I. Schiermeyer, M. Tewes, Longest paths and longest cycles in graphs with large degree sums, Graphs Combin. 18 (2002) 633-643]. In this paper, we investigate graphs G with p(G)−c(G) at most 1 or at most 2, but with no hamiltonian paths. Let G be a 2-connected graph of order n, which has no hamiltonian paths. We show two results as follows: (i) if , then p(G)−c(G)≤1, and (ii) if σ4(G)≥n+3, then p(G)−c(G)≤2. |
| |
Keywords: | Relative length Longest path Longest cycle |
本文献已被 ScienceDirect 等数据库收录! |
|