セミナー

組合せ論セミナー

タイトル	Hypohamiltonian Graphs
開催日時	2016年5月30日 16:30～18:00
主催者
講演者	Carol Zamfirescu氏 (Ghent University, Belgium)
場所	14-631A
内容	A graph is hypohamiltonian if it is non-hamiltonian but, when omitting an arbitrary vertex, it becomes hamiltonian. A problem of Sousselier from 1963 initiated the study of these graphs. The smallest hypohamiltonian graph is the famous Petersen graph on 10 vertices. Chv\'{a}tal asked in 1972 whether there exist planar hypohamiltonian graphs, while Gr\"{u}nbaum conjectured that these graphs do not exist. An infinite family of such graphs was subsequently found by Thomassen, the smallest among them having order 105. We present the progress made towards finding the smallest planar hypohamiltonian graphs, while pointing out the importance of Grinberg's Criterion and discussing related problems on longest paths and longest cycles. We will also treat the planar cubic case, girth restrictions and hypohamiltonian graphs in the context of crossing numbers. A theorem concerning the number of cubic vertices in a planar hypohamiltonian graph---where we use a recent result obtained together with Gunnar Brinkmann and strengthen a theorem of Thomassen---will also be presented. In the second part, we look at almost hypohamiltonian graphs and their connection to hypohamiltonian graphs. Once more, the planar case plays an exceptional role. We study Gallai's problem on longest paths and its connection with almost hypotraceable graphs---combining our techniques with computational results of McKay, we shall determine the smallest 3-connected cubic almost hypotraceable graph. If time permits, we shall also discuss non-hamiltonian graphs in which every vertex-deleted subgraph is traceable, a class encompassing hypohamiltonian and hypotraceable graphs. Connections will be drawn with recent work of Wiener, and we will present solutions to certain problems raised by him related to the minimum leaf number.
資料
URL