کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6423669 | 1632577 | 2016 | 6 صفحه PDF | دانلود رایگان |
A graph G is hypohamiltonian/hypotraceable if it is not hamiltonian/traceable, but all vertex deleted subgraphs of G are hamiltonian/traceable. Until now all hypotraceable graphs were constructed using hypohamiltonian graphs; extending a method of Thomassen [C. Thomassen, Hypohamiltonian and hypotraceable graphs, Discrete Mathematics 9 (1974), 91-96] we present a construction that uses so-called almost hypohamiltonian graphs (nonhamiltonian graphs, whose vertex deleted subgraphs are hamiltonian with exactly one exception). As an application, we construct a planar hypotraceable graph of order 138, improving the best known bound of 154 [M. Jooyandeh, B. D. McKay, P. R. J. ÃstergÃ¥rd, V. H. Pettersson, C. T. Zamfirescu, Planar Hypohamiltonian Graphs on 40 Vertices, J. Graph Theory DOI: 10.1002/jgt.22015 (2016)]. We also prove a structural type theorem showing that hypotraceable graphs possessing some connectivity properties are all built using either Thomassen's or our method.
Journal: Electronic Notes in Discrete Mathematics - Volume 54, October 2016, Pages 127-132