1-Hamilton-connected claw-free graphs
Presented by Prof. Zdenek RYJACEK
Type: Oral presentation
Track: Graph Theory
A graph G is Hamilton-connected if G has a hamiltonian (u,v)-path for any pair of vertices u, v, and, for an integer k, a graph G is k-Hamilton-connected if the graph G-X is Hamilton-connected for every set X of vertices with |X|=k. Specifically, G is 1-Hamilton-connected if G-x is Hamilton-connected for every vertex x of G. Obviously, a Hamilton-connected graph is 3-connected, and a k-Hamilton-connected graph is (k+3)-connected. In the talk we first present a closure concept for 1-Hamilton-connectedness in claw-free graphs such that, if G' is a closure of a claw-free graph G, then (i) G' is 1-Hamilton-connected if and only if G is 1-Hamilton-connected, (ii) G' is the line graph of a multigraph, and (iii) for some vertex x of G, G'-x is the line graph of a multigraph with at most two triangles or at most one double edge. We then discuss some applications of the closure concept to some equivalent versions and partial solutions of the Thomassen's Conjecture (every 4-connected line graph is hamiltonian). Joint work with Petr Vrana, Pilsen.