首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 urn:x-wiley:03649024:media:jgt21743:jgt21743-math-0001 is Hamilton‐connected for every vertex urn:x-wiley:03649024:media:jgt21743:jgt21743-math-0002. In the article, we introduce a closure concept for 1‐Hamilton‐connectedness in claw‐free graphs. If urn:x-wiley:03649024:media:jgt21743:jgt21743-math-0003 is a (new) closure of a claw‐free graph G, then urn:x-wiley:03649024:media:jgt21743:jgt21743-math-0004 is 1‐Hamilton‐connected if and only if G is 1‐Hamilton‐connected, urn:x-wiley:03649024:media:jgt21743:jgt21743-math-0005 is the line graph of a multigraph, and for some urn:x-wiley:03649024:media:jgt21743:jgt21743-math-0006, urn:x-wiley:03649024:media:jgt21743:jgt21743-math-0007 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
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号