9-13 June 2013
Koper, Slovenia
UTC timezone
Home > Timetable > Contribution details
PDF | XML

1-Hamilton-connected claw-free graphs

Presented by Prof. Zdenek RYJACEK
Type: Oral presentation
Track: Graph Theory

Content

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.

Place

Location: Koper, Slovenia

Primary authors

More