グラフ・ネットワークにおける理論と最適化グループセミナー
日時
2013年2月13日 (水) 17:00 ～ 18:00
場所
国立情報学研究所 2208号室
講演者
Petr Vrana 先生（University of West Bohemia）
タイトル
A closure for 1-Hamilton-connectedness in claw-free graphs
アブストラクト
A graph G is 1-Hamilton-connected if G – x is Hamilton-connected for every vertex x \in V (G). In the paper we introduce a closure concept for 1-Hamilton-connectedness in claw-free graphs. This new closure of a claw-free graph G is the line graph of a multigraph H such that, for some x, L^{-1}(G – x) has at most two triangles or one double edge, and is 1-Hamilton-connected if and only if G is 1-Hamilton-connected. 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.
