Document Type
Lecture
Publication Date
4-15-2015
Abstract
In 1984, Bauer proposed the problems of determining best possible su cient 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 su cient 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) Let G be a simple graph on n vertices and ab be real numbers with 0 < a 1. There exist an integer N(ab) and a nite family F(ab) such that if n N(ab) and if dG(u) + dG(v) an+b for any uv V(G) with uv E(G), then either L(G) is hamiltonian-connected, or (L(G)) 2, or G can be contracted to a member in F(ab). (ii) Let G be a simple graph on n vertices. If dG(u) + dG(v) n 4 2 for any uv V(G) with uv E(G), then for su ciently large n, either L(G) is hamiltonian-connected, or (L(G)) 2, or G can be contracted to W8, the Wagner graph. (iii) Let G be a simple triangle-free (or bipartite) graph on n vertices. If dG(u) + dG(v) n 8 for any uv V(G) with uv E(G), then for su ciently large n, either L(G) is hamiltonian-connected, or (L(G)) 2, or G can be contracted to W8, the Wagner graph. This is joint work with Jianping Liu, Keke Wang and Hongjian Lai.
Relational Format
presentation
Recommended Citation
Yu, Aimei, "Hamiltonian-Connected Line Graphs with Given Degree Sums" (2015). Combinatorics Seminar. 37.
https://egrove.olemiss.edu/math_combinatorics/37
