科研之友
微信
新浪微博
Facebook
分享链接
摘要
In 1984, Bauer proposed the problems of determining best possible sufficient conditions on the vertex degrees of a simple graph (or a simple bipartite graph, or a simple triangle free graph, respectively) G to ensure that its line graph L(G) is hamiltonian. We investigate the problems of determining best possible sufficient conditions on the vertex degrees of a simple graph G to ensure that its line graph L(G) is hamiltonian-connected, and prove the following. @@@ (i) For any real numbers a, b with 0 < a < 1, there exists a finite family F(a, b) such that for any connected simple graph G on n vertices, if d(G)(u)+d(G)(v) >= an + b for any u, v is an element of V(G) with uv is not an element of E(G), then either L(G) is hamiltonian-connected, or kappa(L(G)) <= 2, or L(G) is not hamiltonian-connected, kappa(L(G)) >= 3 and G is contractible to a member in F(a, b). @@@ (ii) Let G be a connected simple graph on n vertices. If d(G)(u) + d(G)(v) >= n/4 - 2 for any u, v is an element of V(G) with uv is not an element of E(G), then for sufficiently large n, either L(G) is hamiltonian-connected, or kappa(L(G)) <= 2, or L(G) is not hamiltonian-connected, kappa(L(G)) >= 3 and G is contractible to W-8, the Wagner graph. @@@ (iii) Let G be a connected simple triangle-free (or bipartite) graph on n vertices. If d(G)(u) + d(G)(v) >= n/8 for any u, v is an element of V(G) with uv is not an element of E(G), then for sufficiently large n, either. L(G) is hamiltonian-connected, or kappa(L(G)) <= 2, or L(G) is not hamiltonian-connected, kappa(L(G)) >= 3 and G is contractible to W-8, the Wagner graph.
