Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.endm.2016.09.023 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
hypotraceable graph,hypohamiltonian graph,almost hypohamiltonian graph | Graph theory,Discrete mathematics,Indifference graph,Combinatorics,Hamiltonian (quantum mechanics),Vertex (geometry),Coxeter graph,Hypohamiltonian graph,Chordal graph,Pathwidth,Mathematics | Journal |
Volume | ISSN | Citations |
54 | 1571-0653 | 2 |
PageRank | References | Authors |
0.43 | 1 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gábor Wiener | 1 | 64 | 10.65 |