A Closure for 1‐Hamilton‐Connectedness in Claw‐Free Graphs |
| |
Authors: | Zdeněk Ryjá?ek Petr Vrána |
| |
Institution: | 1. DEPARTMENT OF MATHEMATICS, UNIVERSITY OF WEST BOHEMIA, CZECH REPUBLIC;2. INSTITUTE FOR THEORETICAL COMPUTER SCIENCE (ITI), CHARLES UNIVERSITY, CZECH REPUBLIC;3. SCHOOL OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE, THE UNIVERSITY OF NEWCASTLE, AUSTRALIA |
| |
Abstract: | A graph G is 1‐Hamilton‐connected if is Hamilton‐connected for every vertex . In the article, we introduce a closure concept for 1‐Hamilton‐connectedness in claw‐free graphs. If is a (new) closure of a claw‐free graph G, then is 1‐Hamilton‐connected if and only if G is 1‐Hamilton‐connected, is the line graph of a multigraph, and for some , is the line graph of a multigraph with at most two triangles or at most one double edge. As applications, we prove that Thomassen's Conjecture (every 4‐connected line graph is hamiltonian) is equivalent to the statement that every 4‐connected claw‐free graph is 1‐Hamilton‐connected, and we present results showing that every 5‐connected claw‐free graph with minimum degree at least 6 is 1‐Hamilton‐connected and that every 4‐connected claw‐free and hourglass‐free graph is 1‐Hamilton‐connected. |
| |
Keywords: | 1‐Hamilton‐connected claw‐free graph closure line graph Thomassen Conjecture |
|
|