首页 | 本学科首页   官方微博 | 高级检索  
     


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 View the MathML source, 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号