Name
Abstract | ||
|---|---|---|
A graph G is hypohamiltonian/hypotraceable if it is not hamiltonian/traceable, but all vertex-deleted subgraphs of G are hamiltonian/traceable. All known hypotraceable graphs are constructed using hypohamiltonian graphs; here we present a construction that uses so-called almost hypohamiltonian graphs (nonhamiltonian graphs, whose vertex-deleted subgraphs are hamiltonian with exactly one exception, see [15]). This construction is an extension of a method of Thomassen [11]. As an application, we construct a planar hypotraceable graph of order 138, improving the best-known bound of 154 [8]. 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. We also prove that if G is a Grinbergian graph without a triangular region, then G is not maximal nonhamiltonian and using the proof method we construct a hypohamiltonian graph of order 36 with crossing number 1, improving the best-known bound of 46 [14]. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1002/jgt.22173 | JOURNAL OF GRAPH THEORY |
Keywords | Field | DocType |
hamiltonian graph,hypohamiltonian graph,hypotraceable graph | Graph,Combinatorics,Hamiltonian path,Hypohamiltonian graph,Mathematics | Journal |
Volume | Issue | ISSN |
87 | 4 | 0364-9024 |
Citations | PageRank | References |
1 | 0.36 | 4 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gábor Wiener | 1 | 64 | 10.65 |