Hamiltonicity of graphs on surfaces in terms of toughness andscattering number – A survey
Kenta Ozeki
Faculty of Environment and Information Sciences,
Yokohama National University, Japan.
e-mail: ozeki-kenta-xr@ynu.ac.jp

Abstract
This paper aims to survey Hamiltonicity of graphs on surfaces, including stronger(e.g. Hamiltonian-connectedness) and weaker (e.g. containing Hamiltonian paths andspanning trees with certain conditions) properties. Toughness and scattering number
conditions are necessary conditions for graphs to have such properties. Since every kconnected graph on a surface F 2 satisﬁes some toughness and scattering number condition, we can expect that “every k-connected graph on a surface F 2 satisﬁes the property
P”. We explain which triple (k, F 2 , P) makes the statement true in the viewpoint of thetoughness and scattering number of graphs,

Keywords: Hamiltonian cycles, Spanning trees, Toughness, Scattering number, Plane graphs
MSC 2010: 05C05, 05C10, 05C38, 05C45,

1Introduction

This paper aims to survey Hamiltonicity of graphs on surfaces, including stronger (e.g. Hamiltonianconnectedness) and weaker (e.g. containing Hamiltonian paths and spanning trees with certain conditions) properties. In the viewpoint of the toughness and scattering number ofgraphs, we discuss which triple (k, F 2 , P) makes the statement “every k-connected graph ona surface F 2 satisﬁes the property P” be true.

2

Preliminaries

2.1

Hamiltonicity

A cycle or a path C in a graph G is said to be Hamiltonian if C visits all vertices in G. A
graph with a Hamiltonian cycle is said to be Hamiltonian. Because of its relation to several
problems such as the Travelling Salesman Problem, Hamiltonicity of graphs is one of theimportant topics in graph theory. In particular, Hamiltonicity of planar graphs or graphs on
surfaces is related to the Four Color Theorem, and hence this has attracted many researchers.
For example, Tait [95] claimed to show in 1880 that “if every 3-connected planar cubic graphis Hamiltonian, then every planar graph can be colored by four colors”. Note that it waslater shown that the assumption of Tait’s theorem does not hold (see [103] for example), andhence this approach does not reach to a solution to the Four Color Problem. However, sincethen, Hamiltonicity of graphs on surfaces has attracted wide attention.

1

For example, Whitney [105] proved in 1931 that every 4-connected plane triangulation is
Hamiltonian, and Tutte [101] improved this result to 4-connected planar graphs;
Theorem 1 (Tutte [101]) Every 4-connected planar graph is Hamiltonian.
Many results have been shown, and we will introduce those in this survey.
A graph G is said to be Hamiltonian-connected if for every pair of distinct vertices x andy in G, there is a Hamiltonian path in G between x and y. Note that any Hamiltonianconnected graph is Hamiltonian and any Hamiltonian graph contains a Hamiltonian path.
We denote properties related to Hamiltonicity by PH , PHP , PHC as follows;
PH : Containing a Hamiltonian cycle,
PHP : Containing a Hamiltonian path,
PHC : Being Hamiltonian-connected.

2.2

The condition (∗), toughness and scattering number

We denote by c(H) the number of components of a graph H. For a graph G and real numbersa and b, consider the following condition;(∗)

c(G − S) ≤ a|S| + b for any S ⊆ V (G) with c(G − S) ≥ 2.

The toughness of a graph G is the minimum of a satisfying (∗) with b = 0. Chvátal [26](see also [27]) in 1973 introduced the concept of toughness and conjectured that there exists
a constant t0 such that every graph satisfying (∗) with (a, b) = ( t10 , 0) is Hamiltonian. Thisconjecture is still open. Chvátal ﬁrst conjectured t0 > 3/2 suﬃces, but some counterexamples
were found (e.g. see [38]). Bauer, Broersma and (Veldman[8] showed that there exist non)
Hamiltonian graphs satisfying (∗) with (a, b) = 49 , 11.
Thus,
t0 ≥ 9/4 even if Chvátal’s
9conjecture holds. See [7, 15] for more information on toughness.
On the other hand, the scattering number of a graph G is deﬁned as the minimum of bsatisfying (∗) with a = 1. This concept was deﬁned by Jung [56], as the “additive dual” forthe concept of toughness.
As pointed out in [26, 56], it is easy to see the following necessary condition for Hamiltonicity.
Proposition 2 Let G be a graph.
• If G contains a Hamiltonian path, then G satisﬁes (∗) with (a, b) = (1, 1).
• If G is Hamiltonian, then G satisﬁes (∗) with (a, b) = (1, 0).
• If G is Hamiltonian-connected, then G satisﬁes (∗) with (a, b) = (1, −1).
In this survey, we focus on several properties which have the condition (∗) as a necessary
condition, such as those in Proposition 2. For a property P, we deﬁne the real numbers aPand bP as follows;{}(aP , bP ) = inf (a, b) : Every graph with the property P satisﬁes (∗) with (a, b) ,where the inﬁmum is taken in the lexicographical order. Note that some properties P do nothave aP and bP , but we do not consider such properties P in this survey.

2

For example, Proposition 2 implies (aPH , bPH ) ≤ (1, 0), where ≤ represents the lexicographical order. On the other hand, consider the complete bipartite graph Km,m withm ≥ 2, which is Hamiltonian. We see that for any a < 1 and any real number b, if we takea large integer m satisfying (1 − a)m > b, then c(Km,m − S) = m > am + b = a|S| + b,
where S is the set of vertices contained in one partite set. Furthermore, for any b < 0,c(Km,m − S) = m > m + b = |S| + b for the same vertex set S. Thus, for any a < 1 andany b, and for a = 1 and any b < 0, there exists a Hamiltonian graph that does not satisfy(∗) with (a, b). These show that (aPH , bPH ) = (1, 0). Similarly, we see (aPHP , bPHP ) = (1, 1)
and (aPHC , bPHC ) = (1, −1), by Km,m+1 and the graph obtained from the complete bipartite
graph Km,m−1 by adding all possible edges in the larger bipartite set for a suﬃciently large
integer m, respectively．
In addition, the property of containing a spanning tree with bounded maximum degree
is also related to the condition (∗). For k ≥ 2, a k-tree is a tree with maximum degree at
most k. A Hamiltonian path is nothing but a spanning 2-tree, and hence a spanning k-tree isrelated to Hamiltonicity. We denote by Pk-tree the property of containing a spanning k-tree.
For this property, it is known that (aPk-tree , bPk-tree ) = (k − 1, 1), see [79, Proposition 5] for a
proof. We refer the readers to a survey [79] on spanning trees. Note that Win [106] showedthat every graph satisfying (∗) with (a, b) = (k − 2, 2) contains a spanning k-tree, and a shortproof was found in [37].
As an extension of a spanning k-tree, we deﬁne the following concept. For k ≥ 2 and atree T , the total excess of T from k, denoted by te(T, k), is deﬁned as∑{}te(T, k) =max degT (v) − k, 0 ,v∈V (T )where degT (v) is the degree of a vertex v in T . Note that a tree T satisﬁes te(T, k) = 0 if
and only if T is a k-tree. Furthermore, a tree T satisﬁes te(T, 2) ≤ t if and only if T has at
most (t + 2) leaves. We denote by P(k,t)-tree the property of containing a spanning tree of
which the total excess from k is at most t. Similarly to the case of Pk-tree , it can be shownthat (aP(k,t)-tree , bP(k,t)-tree ) = (k − 1, t + 1).
A spanning closed k-walk, which is a spanning closed walk visiting every vertex at most ktimes, is related to a spanning k-tree. By the deﬁnition, a spanning closed 1-walk is nothing
but a Hamiltonian cycle. Note that if a graph contains a spanning k-tree, then it contains aspanning closed k-walk, and if a graph contains a spanning closed k-walk, then it contains aspanning (k + 1)-tree (see [54]). Let Pk-walk be the property of containing a spanning closed
k-walk. Then we see (aPk-walk , bPk-walk ) = (k, 0). Recall that (aPk-tree , bPk-tree ) = (k − 1, 1).
Thus, we expect that the property of containing a spanning closed k-walk is close to theproperty of containing a spanning (k + 1)-tree, while the former is stronger than the latter.
This expectation will appear in Section 5.2 (see also [54]).

2.3

Graphs on Surfaces

We refer to Mohar and Thomassen [66] for the detail of surfaces and graphs on them.
A surface F 2 is a connected compact 2-dimensional manifold without boundary. By theclassiﬁcation of surfaces, F 2 is either an orientable surface of genus t ≥ 0, denoted by St , ora nonorientable surface of genus k ≥ 1, denoted by Nk . The Euler genus of a surface F 2 ,denoted by g(F 2 ), is deﬁned as{
2t if F 2 is the orientable surface St ,2g(F ) =
k if F 2 is the nonorientable surface Nk .
3

Note that S0 is the sphere, N1 is the projective plane, S1 is the torus, and N2 is the Kleinbottle, where their Euler genera are 0, 1, 2 and 2, respectively.
A graph G on a surface F 2 means an embedding of G in F 2 , that is, a drawing of G on
F 2 in which the edges do not cross each other. We can regard plane graphs also as graphs on
the sphere through the inverse of the stereographic projection. Euler’s formula states thatany graph G on F 2 satisﬁes that
|V (G)| − |E(G)| + |F (G)| ≥ 2 − g(F 2 ).
(Note that if G is 2-cell embedding in F 2 , that is, every face is homeomorphic to a disk, thenthe equality holds.) The following is am important relation between the condition (∗) andgraphs on surfaces.
Proposition 3 (Schmeichel and Bloom [91]) Let k ≥( 3 and let G2 be a) k-connected
2g(F ) − 42,.
graph on a surface F 2 . Then G satisﬁes (∗) with (a, b) =k−2
k−2
Proof. We follows the proof by Goddard, Plummer and Swart [47].
Let S ⊆ V (G), and let c be the number of components in G − S (that is, c = c(G − S)).
We construct the graph H by contracting each component in G − S to one vertex, deleting
all obtained multiple edges and loops, and deleting all edges connecting two vertices in
S. Then H is a bipartite graph still on the surface F 2 . Hence, Euler’s formula directly
implies |E(H)| ≤ 2(|S| + c) + 2g(F 2 ) − 4. Since G is k-connected, each component in G − S
has at least k neighbors in S, and hence |E(H)| ≥ kc. These two inequalities imply that2 )−42c(G − S) = c ≤ k−2|S| + 2g(F□k−2 , as desired.
Consider a triangulation H of F 2 , and take the face subdivision of H, that is, add a
new vertex to each face and connected it to all the vertices on the facial cycle. Let G be
the obtained graph, which is a triangulation of F 2 . By Euler’s formula, we can calculatec(G − V (H)) = |F (H)| = 2|V (H)| + 2g(F 2 ) − 4. This means that G satisﬁes the boundobtained in Proposition 3 with equality when S = V (H) for k = 3. Similarly, if we begin withquadrangulations with minimum degree at least 2, as H, then we can construct triangulations
G of F 2 satisfying the bound obtained in Proposition 3 with equality when S = V (H) fork = 4. To construct 5-connected ones, we may be more careful to choose graphs H, but atleast some pentangulations with minimum degree at least 3 work. These show the following,that is, Proposition 3 is in some sense best possible.
Proposition 4 For k = 3, 4 or 5 and any surface F 2 , there exist inﬁnitely many k-connected
triangulations G on F 2 with S ⊆ V (G) such that c(G − S) ≥ 2 andc(G − S) =22g(F 2 ) − 4
|S| +
.
k−2
k−2

To show the same conclusion for the case k = 6, we need to begin with some hexangulations of a surface F 2 with minimum degree at least 3. (Otherwise, after the face subdivision,
the vertices in H will have degree at most 4, and hence it is not 5-connected.) Such hexangulations exist for any surfaces F 2 with g(F 2 ) ≥ 2, but do not exist for the sphere andthe projective plane. Similarly, for the case k = 7, we need to begin with a heptangulation
with minimum degree at least 4. Note that for each surface F 2 , there are only ﬁnitely many
heptangulations. In fact, there are only ﬁnitely many 7-connected graphs on F 2 . Thus, we
do not consider the case k ≥ 7 in this survey.
4

On the other hand, it should be worthwhile to notice that for k = 3, 4 or 5 and any surface
F 2 , there exist inﬁnitely many k-connected triangulations G on F 2 that satisfy the boundobtained in Proposition 3 with strict inequality for any S ⊂ V (G). For example, consider the
triangulation obtained from the face subdivision of a 4-connected triangulation by removingsome added vertices. We can check that such triangulations satisfy the above condition. We
leave the detail to the readers.
A closed curve γ on a surface is said to be contractible if γ bounds a 2-cell region on F 2 ;Otherwise, γ is essential. The representativity rep(G) of a graph G on a surface F 2 is theminimum number of intersecting points of G and γ, where γ ranges over all essential closed
curves on F 2 . (If F 2 is the sphere, then we deﬁne rep(G) = ∞.) Graphs on surfaces with
suﬃciently large representativity are sometimes informally called locally planar graphs, andknown to have properties similar to plane graphs. Actually, by the same way as Proposition
3, we obtain the next proposition.
2
Proposition 5 Let k ≥ 3, a0 > k−2
and b0 be a real number. Then for any surface F 2 , there
exists a constant r such that every k-connected graph G on F 2 with rep(G) ≥ r satisﬁes (∗)
with (a, b) = (a0 , b0 )．

Note that for each k, Archdeacon, Hartsﬁeld and Little [1] constructed a k-connected triangulation Gk embedded in some orientable surface F 2 with S ⊆ V (Gk ) such that rep(Gk ) ≥k and c(Gk − S) ≥ k|S|. Note that the genus of F 2 depends on K, and this shows that theconstant r in Proposition 5 must depend on the surface F 2 .

2.4

Purpose of the study

This survey investigates for k ≥ 3, a surface F 2 , and several properties P, such as PH , PHP ,PHC , whether the statement thatevery k-connected graph on F 2 satisﬁes P
holds or not. In fact, this statement does not hold for some triples (k, F 2 , P), since as in
Proposition 2, some properties P requires (∗) with (a, b) = (aP , bP ) as a necessary condition,
but Proposition 4 shows that for some surface F 2 , there are k-connected graphs on F 2 that
do not satisfy (∗) with aP and bP .
However, we expect that the statement above holds for (k, F 2 , P) if all k-connected graphs
on F 2 satisfy (∗) with (a, b) = (aP , bP ). We introduce several results and conjectures, which
supports this expectation. In this sense, the relation between Hamiltonicity and the connectivity of graphs on surfaces seems to be based on the condition (∗). See also the survey[32].
For example, consider the sphere S 2 , which satisﬁes g(S 2 ) = 0. Proposition 4 implies
that there are inﬁnitely many 4-connected graphs on the sphere S 2 satisfying the equality in(∗) with (a, b) = (1, −2). Since bPH = 0 ≥ −2 = g(S 2 ) − 2, all 4-connected graphs on thesphere S 2 satisfy (∗) with (a, b) = (aPH , bPH ), which is a necessary condition to be PH . Thus,
one can expect that all 4-connected graphs on the sphere S 2 are Hamiltonian. In fact, Tutte
showed that this expectation indeed holds, see Theorem 1.
This situation can be seen for several triples (k, F 2 , P), and we discuss which triple makes
the statement “every k-connected graph on F 2 satisfy (∗) with (a, b) = (aP , bP ) satisﬁes P”
true.

5

2.5

Remark on non-Hamiltonian planar graphs

As in the previous subsection, our aim is to show some properties related to Hamiltonicity
in k-connected graphs on a surface in terms of the condition (∗). One may wonder thatinstead of the k-connected condition, we can use directly the condition (∗) and guarantee
Hamiltonicity. However, this does not seem to have a good behavior.
It is well-known that every graph satisfying (∗) with (a, b) = (t, 0) is ⌈2/t⌉-connected(see [26]). Thus, Theorem 1 directly implies that every planar graph satisfying (∗) with(a, b) = (t, 0) for t < 23 is Hamiltonian. Nishizeki [71] constructed non-Hamiltonian plane
triangulations satisfying (∗) with (a, b) = (1,( 0).) This was later extended to non-Hamiltonian
planar graphs satisfying (∗) with (a, b) = 23 , 0 by Harant( 2 2 ) [51] and also to non-Hamiltonian
plane triangulations satisfying (∗) with (a, b) = 3 , 3 by Owens [74]. (It is an open
problem (whether
there exists a non-Hamiltonian plane triangulation satisfying (∗) with)2
(a, b) = 3 , 0 .) Thus, in this sense, Theorem 1 in terms on 4-connected planar graphs
is more essential than the statement in terms of the condition (∗).

4-connectedness and properties P with aP = 1

3

In this section, we focus on 4-connected graphs on surfaces. By Proposition 3,
every 4-connected graph on a surface F 2 satisﬁes (∗) with (a, b) = (1, g(F 2 ) − 2),and by Proposition 4, there are inﬁnitely many 4-connected graphs on F 2 that satisfy theequality in (∗) with (a, b) = (1, g(F 2 ) − 2). Therefore, for properties P with aP = 1, suchas PH , PHP and PHC , there are some surfaces F 2 such that every 4-connected graph on
F 2 satisﬁes (∗) with (a, b) = (aP , bP ). On the other hand, depending on the value of bP ,Proposition 4 implies that there are some surfaces F 2 such that some 4-connected graphs on
F 2 do not satisfy (∗) with (a, b) = (aP , bP ).
For example, consider the torus T 2 , which satisﬁes g(T 2 ) = 2. Proposition 4 implies that
there are inﬁnitely many 4-connected graphs on the torus T 2 satisfying the equality in (∗)
with (a, b) = (1, 0). Since bPHC = −1 < 0 = g(T 2 ) − 2, those are not Hamiltonian-connected.
Because of this reason, we will deal with only the triple (4, F 2 , P) that satisfy aP = 1 andbP ≥ g(F 2 ) − 2.

3.1

Hamiltonian paths, Hamiltonian cycles and Hamiltonian-connectedness

We ﬁrst focus on the properties PH , PHP and PHC . We summarize the known results andconjectures in Table 1. As explained above, depending on the Euler genus g(F 2 ), somesurfaces F 2 may admit 4-connected graphs on F 2 that do not satisfy (∗) with (a, b) = (aP , bP ).
When such graphs exist, we represent “×” for the corresponding cell in Table 1, which meansthat there exist inﬁnitely many counterexamples to the corresponding statement. The cellwith “⃝” means that the corresponding statement holds, which was shown in the referencein the cell. (e.g. Thomassen [99] proved that every 4-connected planar graph is Hamiltonianconnected.) The cell with “?” means that it is still open whether the corresponding statement
holds, which has been conjectured in designated literature.
As explianed in Section 2.1, Whitney [105] proved that every 4-connected plane triangulation is Hamiltonian before Tutte’s theorem for 4-connected planar graphs (Theorem 1).
Note that later, Tutte [102] himself gave a simpler proof.
1
2This statement was known as Grünbaum’s conjecture [50] before Thomas and Yu [96].
This statement was known as Dean’s conjecture [29] before Kawarabayashi and Ozeki [61]．

6Table 1: Hamiltonicity of 4-connected graphs on a surface.
PHP (bPHP = 1)

PH (bPH = 0)

Sphere (plane)g(F 2 ) = 0
Projective planeg(F 2 ) = 1

Tutte [101]Thomas & Yu [96]1

Torusg(F 2 ) = 2

Thomas, Yu& Zang [98]Klein bottleg(F 2 ) = 2
N3g(F 2 ) = 3
Other surfacesg(F 2 ) ≥ 4?

?

PHC (bPHC = −1)
Thomassen [99]Kawarabayashi& Ozeki [61]2Grünbaum [50]Nash-Williams [70]?

?

Chiba and Nishizeki [23] pointed out an omission in the proof of Thomassen’s result [99]stating that every 4-connected planar graph is Hamiltonian-connected, and ﬁxed it. See
also [72, Chapter 10]. Other proofs for the theorem can be found in [64, 75]. Based on
Thomassen’s proof, Chiba and Nishizeki [24] presented an algorithm to ﬁnd a Hamiltonian
cycle in 4-connected planar graphs, which was an improvement of the algorithms in [2, 49].
Recently, further algorithms can be found in [10, 92, 93].
As in Table 1, there are several results on Hamiltonicity of 4-connected graphs on surfaces,
but still some open problems remain. The following is the most important conjecture in thisﬁeld.
Conjecture 6 (Grünbaum [50], Nash-Williams [70]) Every 4-connected graph on thetorus is Hamiltonian.
The diﬃculty of Conjecture 6 seems to come from the proof method for 4-connected
graphs on the sphere and the projective plane to be PH . Because of inductive arguments, allsuch results have been shown by proving a stronger property P′ than PH (e.g. the property ofcontaining a Hamiltonian cycle passing through a prescribed edge), which satisﬁes (aP′ , bP′ ) =(1, −1). However, this method does not work for the toroidal case, since there are inﬁnitely
many 4-connected graphs on the torus that do not satisfy (∗) with (a, b) = (1, −1) as in
Proposition 4. Thus, we cannot expect to use the same idea. This seems to be a diﬃculty inproving Conjecture 6.
Note that Proposition 3 implies that for a 4-connected graph G on the torus, G does notsatisfy (∗) with (a, b) = (1, −1) if and only if the equality in (∗) with (a, b) = (1, 0) holds
for some S ⊆ V (G). Considering this situation, Fujisawa, Nakamoto and Ozeki proved thefollowing theorem.
Theorem 7 (Fujisawa, Nakamoto and Ozeki [41, 68]) Let G be a 4-connected graphon the torus. If the equality in (∗) with (a, b) = (1, 0) holds for some S ⊆ V (G), then G is
Hamiltonian.
Thus, to solve Conjecture 6, it suﬃces to focus on 4-connected graphs on the torus thatsatisfy (∗) with (a, b) = (1, −1), and we may be able to use the proof method that has been7

succeeded for the case of the sphere and the projective plane. Conjecture 6 is still open, but
the author expects that it will be solved by this argument.

3.2

Planar graphs and properties P with (aP , bP ) = (1, −2)

If we restrict ourselves to 4-connected planar graphs G, then Proposition 3 implies that G
satisﬁes (∗) with (a, b) = (1, −2). Since (aPHC , bPHC ) = (1, −1), we expect that every 4connected planar graph has properties stronger than being Hamiltonian-connected such thatthey require (∗) with (a, b) = (1, −2) as a necessary condition. In fact, the following results
are obtained;• Every 4-connected planar graph G with at least 5 vertices satisﬁes that for any S ⊆V (G) with |S| ≤ 2, G − S is Hamiltonian3 . (This statement was conjectured by
Plummer [82], and shown by Thomas and Yu [96].)• For any two vertices x, y and an edge e with e ̸= xy in a 4-connected planar graph G,
there exists a Hamiltonian path in G connecting x and y through e. (This statement
was shown by Sanders [88].)• For any vertex x in a 4-connected planar graph G, G − x is Hamiltonian-connected.
(This statement can be shown using a result by Sanders [88].)• For vertices u1 , u2 , v1 , v2 , possibly ui = vj for some i, j ∈ {1, 2}, G + {u1 u2 , v1 v2 }contains a Hamiltonian cycle through both u1 u2 and v1 v2 . (This statement was shownby Ozeki and Vràna [78].)
If we write those properties as P2H , PeHC , P1HC and P2eHC’ , respectively, then we obtain(aP2H , bP2H ) = (aPeHC , bPeHC ) = (aP1HC , bP1HC ) = (aP2eHC’ , bP2eHC’ ) = (1, −2) by the same way
as Proposition 2, and the graph obtained from the complete bipartite graph Km,m+2 byadding all possible edges in the larger bipartite set for a suﬃciently large integer m.
Note that any graph with the property P2eHC’ satisﬁes the properties PeHC and P1HC
(the case when u1 = x, u2 = y and v1 v2 = e corresponds to PeHC , and the case whenu2 = v1 = x corresponds to P1HC ). However, it is unknown whether any graph with theproperty P2eHC’ satisﬁes the property P2H . At least there exist inﬁnitely many graphs thatsatisfy the property P2H , but do not satisfy the property P2eHC’ .
A ﬁgure-eight graph consists of two edge-disjoint cycles sharing exactly one vertex. The
shared vertex is called its center. Rosenfeld [86] proved that every 4-connected planar graphcontains a ﬁgure-eight graph as a spanning subgraph with prescribed vertex as a center. This
property P8 is also related to the condition (∗), which satisﬁes (aP8 , bP8 ) = (1, 0). Thus, we
may expect properties stronger than P8 for 4-connected planar graphs.

3.3

Surfaces F 2 with g(F 2 ) ≥ 4 and properties P with bP > 0

As in Table 1, for any surface F 2 with g(F 2 ) ≥ 4, there exist 4-connected graphs on F 2
without Hamiltonian path. This is shown by Proposition 4 and the fact bPHP = 1 < g(F 2 )−2.
However, we would like to ﬁnd some properties that may be weaker than the property PHP but
are related to Hamiltonicity. In this subsection, we focus on P(2,t)-tree , which is equivalent
with the property of containing a spanning tree with at most (t + 2) leaves. Recall that(aP(2,t)-tree , bP(2,t)-tree ) = (1, t + 1). Since every 4-connected graph G on F 2 satisﬁes (∗) with
3

This statement is related to Malkevitch’s conjecture [65] stating that every 4-connected planar graph G
contains a cycle of length l for any 3 ≤ l ≤ |V (G)|, possibly except for l = 4. See also [21].

8()(a, b) = 1, g(F 2 ) − 2 (by Proposition 3), we expect the following conjecture, which was
posed by the author.
Conjecture 8 (Ozeki [76]) For every 4-connected graph G on a surface F 2 with g(F 2 ) ≥ 3,
there exists a spanning tree with at most (g(F 2 ) − 1) leaves.
Recently, using a similar idea to the proof of Theorem 7, Nakamoto and Ozeki [69]showed a partial solution for 4-connected
graphson a surface F 2 with g(F 2 ) ≥ 3 such that()
the equality in (∗) with (a, b) = 1, g(F 2 ) − 2 holds for some S ⊆ V (G).
Considering Proposition 5, every 4-connected locally planar graph on a surface satisﬁes(∗) with a = 2. Ellingham, Gao [33] and Yu [104] focused on this fact, and proved that every
4-connected locally planar graph on a surface contains a spanning 3-tree and a spanning
closed 2-walk. Mohar (see [66, P. 181]) posed the problem whether every 4-connected locallyplanar graph on a surface contains a spanning tree with few leaves, which corresponds toConjecture 8.
Problem 9 (Mohar, see [66]) For any surface F 2 with g(F 2 ) ≥ 3, does there exist a
constant r = r(F 2 ) such that every 4-connected graph G on F 2 with rep(G) ≥ r contains aspanning 3-tree with O(g(F 2 )) leaves?
Böhme, Mohar and Thomassen [12] showed a weaker statement than Problem 9 statingthat for any surface F 2 with g(F 2 ) ≥ 3 and any ε > 0, there exists a constant r = r(F 2 , ε)such that every 4-connected graph G on F 2 with rep(G) ≥ r contains a spanning 3-tree withε|V (G)| leaves.

4

5-connectedness and properties P with aP ≥ 32

In this section, we focus on 5-connected graphs on surfaces. By Proposition 3,()
2
any 5-connected graph on F 2 satisﬁes (∗) with (a, b) = 23 , 2g(F3 )−4 .
Regarding Hamiltonicity of 4-connected graphs on surfaces, there are some open problems
represented by “?” in Table 1 and false statements represented by “×”. However, assuming
the stronger assumption 5-connectedness, we may obtain a result that guarantees Hamiltonicity. For example, Thomas and Yu [97] proved that Conjecture 6 holds if we replace“4-connected” in the assumption with “5-connected”. See Table 2 for more results.
Note that before those results in Table 2, Barnette [5] and Brunet and Richter [18]proved that every 5-connected triangulation of the torus contains a Hamiltonian path, anda Hamiltonian cycle, respectively. Brunet, Nakamoto and Negami [17] proved the sameconclusion holds for 5-connected triangulation of the Klein bottle.
We would like to guarantee Hamiltonicity of 5-connected graphs on a surface F 2 withg(F 2 ) ≥ 4. As explained in the previous section, this is impossible with the assumption of“4-connectedness” by Proposition 4, but Proposition 5 implies that every 5-connected locallyplanar graph on a surface satisﬁes (∗) with (a, b) = (1, 0), which is a necessary condition for
PH . Base on this fact, we expect that the following conjecture holds. (See [66, P. 182] and[104].)
Conjecture 10 For any surface F 2 with g(F 2 ) ≥ 3, there exists a constant r = r(F 2 ) suchthat every 5-connected graph G on F 2 with rep(G) ≥ r is Hamiltonian.

9

Table 2: Hamiltonicity of 5-connected graphs on a surface.
PHP

PH

PHC

Sphere (plane)g(F 2 ) = 0
Projective planeg(F 2 ) = 1
Torusg(F 2 ) = 2
Klein bottleg(F 2 ) = 2
Others (Locally planar)g(F 2 ) ≥ 3

Thomas & Yu [97]?

Kawarabayashi& Ozeki [62]

?

?

?

Thomassen [100]?
?

Conjecture 10 is still open. Yu [104] showed that Conjecture 10 is true if we restrict
ourselves to triangulations. This was conjectured by Thomassen [100]. Kawarabayashi [58]showed that Yu’s result holds even if we replace the conclusion by “Hamiltonian-connected”.
On the other hand, Proposition 3 guarantees that every 5-connected graph on a surface
satisﬁes (∗) with (a, b) = ( 23 , t) for some t. This seems to suggest that such graphs satisfy
some properties P with 1 > aP ≥ 23 . As far as the author knows, there are no results on suchproperties, and hence we leave this as an open problem.
Problem 11 Which properties P satisfy 1 > aP ≥ 23 ? Does every 5-connected planar graph(or 5-connected graph on a surface) satisfy the property P?

53-connectedness and properties P with aP = 2

As explained in the previous sections, 4-connected graphs on surfaces have some properties
related to Hamiltonicity. In this section, we consider the similarity for 3-connected graphs.
By Proposition 3,
any 3-connected graph on F 2 satisﬁes (∗) with (a, b) = (2, 2g(F 2 ) − 4),and by Proposition 4, there are inﬁnitely many 3-connected graphs on F 2 that satisfy theequality in (∗) with (a, b) = (2, 2g(F 2 ) − 4). Therefore, it is natural to show properties P
with aP ≤ 2 in 3-connected graphs on surfaces.

5.1

Spanning trees

We ﬁrst focus on the property P(3,t)-tree , which satisﬁes aP(3,t)-tree = 2, together with someworks on Pk-tree and P(2,t)-tree . We summarize those results in Table 3. The cell with “⃝”means that the corresponding statement holds with best possible value on k or t, while “△”means that the corresponding statement holds but the sharpness is still unknown.
Barnette [6] proved that every 3-connected planar graph contains a spanning 3-tree.
Similarly to the extension from PH to PHC , this result was extended to show the property
that for any vertex x, there exists a spanning 3-tree in which x is a leaf [4, 67]. If wedenote this property by P3-tree+ , then we see that (aP3-tree+ , bP3-tree+ ) = (2, −1). Since every

10Table 3: Spanning trees and closed walks in 3-connected graphs on a surface.
Pk-treeP(2,t)-tree(g(F 2 ) = 2

Barnette [6](k = 3)Barnette [4](k = 3)Barnette [4](k = 3)

Others (locally planar)

Yu [104]

Sphere (plane)g(F 2 ) = 0
Projective planeg(F 2 ) = 1
Torus/K-bottleg(F 2 ) ≥ 3
Othersg(F 2 ) ≥ 3

N. O. O. [67]) 11
t = |G|−73

N. O. O. [67](t = |G|−73(((k = 4)
Ota & Ozeki [73]k=)

N. O. O. [67]t = |G|−33⌈ 2g(F 2 )+4 ⌉)3)

t = |G|+O(1)3

Gao & Richter [43](k = 2)
Gao & Richter [43](k = 2)B. E. G. M. R. [16](k = 2))

Yu [104](k = 3)
Sanders & Zhao [90]Sanders & Zhao [90](Pk-walk?

(

Hasanvand [52]k=

⌈ 2g(F 2 )+2 ⌉)3

3-connected planar graph satisﬁes (∗) with (a, b) = (2, −4) by Proposition 3, we may expectthat a further stronger statement holds.
Proposition 5 implies that there exist inﬁnitely many 3-connected triangulations on asurface F 2 that satisfy the equality in (∗) with (a, b) = (2, 2g(F 2 ) − 4) for some S ⊆ V (G).
Since (aP3-tree , bP3-tree ) = (2, 1), we cannot expect that every 3-connected graph on a surface
F 2 with g(F 2 ) ≥ 3 contains a spanning 3-tree. Thus, we consider the existence of a spanning
tree with higher (but bounded) maximum degree in such graphs. Yu [104] proved thatfor any surface F 2 with g(F 2 ) ≥ 3, there exists a constant r = r(F 2 ) such that every 3connected graph G on F 2 with rep(G) ≥ r contains a spanning 4-tree. Note that before Yu[104], Thomassen [100] proved the same statement for triangulations of orientable surfaces.
Sanders and Zhao [90], and Ota and Ozeki [73] proved that every 3-connected graph G on F 2⌈⌉
2with g(F 2 ) ≥ 3 contains a spanning 2g(F3 )+4 -tree. (Sanders and Zhao [90] proved the caseg(F 2 ) ≥ 38, and later Ota and Ozeki [73] extended this to the case g(F 2 ) ≥ 3.) Note that⌈⌉2
the upper bound “ 2g(F3 )+4 ” of the maximum degree in the obtained spanning tree is best
possible, which is obtained also by the condition (∗). Before [73], Ellingham [32] obtained aweaker conclusion.
Furthermore, similarly to the extension mentioned in Section 3.3, those results on aspanning 3-tree were extended to a spanning tree with bounded total excess from 3 for thecase of surfaces F 2 with g(F 2 ) ≥ 3. Recall that (aP(3,t)-tree , bP(3,t)-tree ) = (2, t + 1). Since
every 3-connected graph on F 2 satisﬁes (∗) with (a, b) = (2, 2g(F 2 ) − 4), we expect that suchgraphs contain a spanning tree T with te(T, 3) ≤ 2g(F 2 ) − 5. This expectation was indeed
true; Kawarabayashi, Nakamoto and Ota [60] proved that every 3-connected locally planargraph G on a surface F 2 contains a spanning 4-tree T with te(T, 3) ≤ 2g(F 2 ) − 5, and Ozeki⌉⌈
2[76] proved that every 3-connected graph G on F 2 contains a spanning 2g(F3 )+4 -tree T
with te(T, 3) ≤ 2g(F 2 ) − 5.
Nakamoto, Oda and Ota [67] considered the existence of a spanning 3-tree with few
number of leaves. Their results are displayed in the column of P(2,t)-tree in Table 3. The
bound on t obtained in [67] is almost best possible, but in the planar case, there is agap. They showed
every 3-connected planar graph contains a spanning{ that }{ 3-tree} T with
|G|−7
|G|−1
te(T, 2) ≤ max
3 , 0 (that is, the number of leaves is at most max
3 , 2 ), while11{
they conjectured that the best possible value would be max{}of leaves could be reduced to at most max |G|−5
,
2
).
3

5.2

|G|−11,0
3}(that is, the number

Spanning closed walks

Recall that we expect that the property of containing a spanning closed k-walk is closed tothe property of containing a spanning (k+1)-tree, while the former is stronger than the latter.
With this expectation in mind, almost all results on Pk-tree in Table 3 were extended to theexistence of a spanning closed k-walk. Gao and Richter [43] proved that every 3-connected
graph on the sphere or the projective plane contains a spanning closed 2-walk. Cui [28] gavelater a short proof to this result. This was extended to 3-connected graphs on the torus
and the Klein bottle by Brunet, Ellingham, Gao, Metzlar and Richter [16]. Some results on
3-connected graphs on surfaces were obtained as in Table 3.
As explained in the previous section, Kawarabayashi, Nakamoto and Ota [60] proved thatevery 3-connected locally planar graph G on a surface F 2 contains a spanning 4-tree T withte(T, 3) ≤ 2g(F 2 ) − 5. They proved the similar result also for a spanning closed 3-walk.
By the above situation, it is natural to think an extension of the result of the property P(2,t)-tree to spanning closed 2-walks, Nakamoto, Oda and Ota [67] implicitly posed thefollowing problem.
Problem 12 Does there exist a constant s0 such that every 3-connected planar graph G
contains a spanning closed 2-walk by which the number of vertices visited twice is at most1
3 |G| + s0 ?
This has not been solved yet. Gao, Richter and Yu [44] (see also [45]) showed that every
3-connected planar graph G contains a spanning closed 2-walk by which every vertex visited
twice is contained in a 3-cut of G. However, since there exist inﬁnitely many 3-connectedplanar graphs such that almost all vertices are contained in a 3-cut, this result does not givea non-trivial bound on the number of vertices visited twice in a spanning closed 2-walk.
Note that for a spanning closed 2-walk W , the number of vertices visited twice by W is
at most 13 |G| + s0 if and only if the length of W is at most 43 |G| + s0 . With this relation inmind, Kawarabayashi and Ozeki [63] proved that every 3-connected planar graph G contains
a spanning closed walk of length at most 4|G|−1, but some vertices may be visited three or3more times.

5.3

Prism-Hamiltonicity

Another related property, so-called prism-Hamiltonian, has been studied. The prism over agraph G is deﬁned as the Cartesian product of G and K2 . Thus, it consists of two copies of G
and a matching joining the corresponding vertices. A graph G is said to be prism-Hamiltonian
if the prism over G is Hamiltonian. It is easy to see that any graph with a Hamiltonian pathis prism-Hamiltonian, and any prism-Hamiltonian graph contains a spanning closed 2-walk,see [57]. Furthermore, if we denote by Pprism the property of being prism-Hamiltonian, thenwe see that (aPprism , bPprism ) = (aP2-walk , bP2-walk ) = (2, 0).
Motivated the theorem that every 3-connected planar graph contains a spanning closed
2-walk (see Section 5.2), Rosenfeld and Barnette [85] (see also [57]) conjectured that every
3-connected planar graph is prism-Hamiltonian, and they proved that any 3-connected cubic planar graph is prism-Hamiltonian4 . Biebighauser and Ellingham [9] proved that this
4

Their proof depends on the Four Color Theorem, which was still unsolved at that time. Without using

12

conjecture holds for triangulations on the sphere, and also the same conclusion holds fortriangulations on the projective plane, the torus, and the Klein bottle. Recently, Spacapan[94] constructed a counterexample to the Rosenfeld-Barnette conjecture.

6

Related results

6.1

Graphs without complete bipartite minors

It is well known that for a 3-connected graph G of order at least 6, G is planar if and only
if G does not contain K3,3 as a minor (see [66, Lemma 2.5.5], together with Kuratowski’s
characterization of planar graphs). Considering this characterization, we here focus on 3connected K3,t -minor-free graphs. Note that the lower bound of the genus of the complete
bipartite graphs, which is directly obtained by Euler’s formula, shows that for any positive
integer g, there is an integer t such that any graph on a surface F 2 with g(F 2 ) = g does nothave a K3,t -minor5 . On the other hand, as pointed out in [22], for any g, Böhme, Maharry andMohar [11] constructed 3-connected K3,7 -minor-free graphs G that cannot be embedded in
an orientable surface F 2 with g(F 2 ) = g. These two results show that studying 3-connected
K3,t -minor graphs is in fact diﬀerent from studying 3-connected graphs on surfaces with large
Euler genus.
Chen, Egawa, Kawarabayashi, Mohar and Ota [20] showed that every 3-connected K3,t minor-free graph satisﬁes (∗) with (a, b) = (t − 1, −2t + 2), and for each odd integer t witht ≥ 3, there exist inﬁnitely many 3-connected K3,t -minor-free graphs that satisfy the equalityin (∗) with (a, b) = (t − 1, −2t + 2). Recall that (aPk-tree , bPk-tree ) = (k − 1, 1). Ota and Ozeki[73] showed the following theorem as expected; for t ≥ 3, every 3-connected K3,t -minor-freegraph contains a spanning (t − 1)-tree when t is even, and a spanning t-tree when t is odd.
Related to this result, it was shown in [36, 35] that every 3-connected K2,4 -minor-freegraph and every 3-connected K2,5 -minor-free planar graph are Hamiltonian, respectively.
Using some properties of 3-connected graphs with no K2,t -minor, which was shown in [25]6 ,we can prove that for any integer t ≥ 3, there exists a constant c(t) such that every 3connected K2,t -minor-free graph contains a spanning tree with at most c(t) leaves. We leave
the proof to the readers.

6.2

Hamiltonicity of 4-connected graphs with small crossing number

The crossing number of a graph G, denoted by cr(G), is the minimum number of edge
crossings over all possible drawings of G on the plane. Note that a graph G is planar if
and only if cr(G) = 0. By the same way to obtain
Proposition
3, we can show that every()
cr(G)−44-connected graph G satisﬁes (∗) with (a, b) = 1,
, which is best possible. With this2in mind, recently Ozeki and Zamﬁrescu [80] conjectured the following;
Conjecture 13 (Ozeki and Zamﬁrescu [80]) Every 4-connected graph G with cr(G) ≤5 is Hamiltonian.
Since any graph G with cr(G) ≤ 1 has an embedding in the projective plane, Conjecture
13 holds by [96] if we replace the condition cr(G) ≤ 5 with cr(G) ≤ 1. Ozeki and Zamﬁrescu
the Four Color Theorem, the same result was proven by Goodey and Rosenfeld [48] with additional conditions
and then ﬁnally, by Fleischner [40]. The most general result on this direction is the following due to Paulraja[81]; any 3-connected cubic graph is prism-Hamiltonian.
5This is related to the map color theorem, see [83, 84].
6
Ding [31] gave a complete structure of K2,t -minor-free graphs.

13

[80] extended this to the case of cr(G) ≤ 2. Since any graph G with cr(G) ≤ 2 can beembedded in the Klein bottle, this is a special case of the open problem stating that every
4-connected graph on the Klein bottle is Hamiltonian, see Table 1. Conjecture 13 is generally
open.

6.3

Hamiltonicity of 3-connected planar graphs

More results on Hamiltonian cycles in planar graphs have been obtained. By Proposition
4, there are some 3-connected planar graphs that do not satisfy (∗) with (a, b) = (1, 0),and hence are not Hamiltonian. However, assuming some conditions which guarantees thenecessary condition, some results are obtained.
As a corollary of Thomassen’s theorem [99], we obtain that every plane triangulation withat most one 3-cut is Hamiltonian (which is also shown by Chen [19]). It was shown that thecondition on “at most one 3-cut” can be replaced with “at most two 3-cuts” (Helden [53]) andalso “at most three 3-cuts” (Jackson and Yu [55]). The same conclusion holds for 3-connectedplanar graphs with at most three 3-cuts (Brinkmann and Zamﬁrescu [14]). There are 3connected plane triangulations with six 3-cuts that do not satisfy (∗) with (a, b) = (a, 0), andhence are not Hamiltonian (see [13]). Thus, it is natural to conjecture that every 3-connectedplanar graph with at most ﬁve 3-cuts is Hamiltonian, and this is still open. The similar workfor the properties of containing a Hamiltonian path or of being Hamiltonian-connected canbe found in a survey [77].
Dillencourt [30] and Sanders [87] gave another type of suﬃcient condition for planargraphs to be Hamiltonian.

6.4

Spanning 2-connected subgraph with bounded degree

A spanning 2-connected subgraph with maximum degree at most k in a graph G is calleda k-covering (or sometimes a k-trestle) of G. While the property of containing a k-covering
does not seem to be directly related to the condition (∗), this is an extension of a spanningk-tree, and there are some works on this topic. First, Barnette [3] proved that every 3connected planar graph contains a 15-covering. This result was later improved by Gao [42]to a 6-covering in a 3-connected graph on a surface F 2 with g(F 2 ) ≤ 2, which is best
possible. Kawarabayashi, Nakamoto and Ota [60, 59] and Sanders and Zhao [89] considered
the existence of a k-covering in 3-connected graphs on surfaces with higher genera.
It is also known that with additional conditions, we can reduce the bound on maximum
degree in a k-covering. Ellingham and Kawarabayashi [34] showed the existence of a 3covering in 4-connected locally planar graphs. Enomoto, Iida and Ota [39] proved that every
3-connected planar graph with minimum degree at least 4 contains a connected subgraph inwhich every vertex has degree 2 or 3.
Note that Gao and Wormald [46] proved that every plane triangulation contains a spanning closed trail (i.e. a spanning closed walk that does not use an edge twice or more) by
which every vertex is visited at most four times. Similarly to a k-covering, this does not seemto be directly related to the condition (∗), but this is an extension of a spanning closed walk.

7

Conclusion

In this survey, we introduce a relation between Hamiltonicity and connectivity of graphs on
surfaces in terms of the condition (∗), which is related to a toughness and scattering number.
In fact, we pose the following informal meta-conjecture.
14

Meta-conjecture For any graph property P related to Hamiltonicity, if all k-connected
graphs on a surface F 2 satisfy the condition (∗) with (a, b) = (aP , bP ), then every k-connected
graph on F 2 satisﬁes the property P.
As explained in Sections 3–5, this meta-conjecture holds for several properties P, and in
Section 6 we show some related results and conjectures that support the meta-conjecture.
In this sense, the relation between Hamiltonicity and the connectivity of graphs on surfaces
seems to be based on the condition (∗).

Acknowledgments
I would thank the referees for carefully reading the paper and helpful comments. This work
was supported by JSPS KAKENHI Grant Number JP18K03391.

References[1] D. Archdeacon, N. Hartsﬁeld and C.H.C. Little, Nonhamiltonian triangulations withlarge connectivity and representativity, J. Combin. Theory Ser. B 68 (1996) 45–55.
[2] T. Asano, S. Kikuchi and N. Saito, A linear algorithm for ﬁnding Hamiltonian cycles in
4-connected maximal planar graphs, Discrete Appl. Math. 7 (1984) l–15.
[3] D.W. Barnette, 2-connected spanning subgraphs of planar 3-connected graphs, J. Combin. Theory Ser. B 61 (1994) 210–216.
[4] D.W. Barnette, 3-trees in polyhedral maps, Israel. J. Math. 79 (1992) 251–256.
[5] D.W. Barnette, Decomposition theorems for the torus, projective plane and Klein bottle,
Discrete Math. 70 (1988) 1–16.
[6] D.W. Barnette, Trees in polyhedral graphs, Canad. J. Math. 18 (1966) 731–736.
[7] D. Bauer, H. Broersma and E. Schmeichel, Toughness in graphs – a survey, Graphs
Combin. 22 (2006) 1–35.
[8] D. Bauer, H. Broersma and H.J. Veldman, Not every 2-tough graph is hamiltonian,
Discrete Appl. Math. 99 (2000) 317–321.
[9] D.P. Biebighauser and M.N. Ellingham, Prism-hamiltonicity of triangulations, J. Graph
Theory 57 (2008) 181–197.
[10] T. Biedl and P. Kindermann, Finding Tutte paths in linear time, preprint (2019)https://arxiv.org/abs/1812.04543[11] T. Böhme, J. Maharry and B. Mohar, Ka,k -minors in graphs of bounded tree-width,
J. Combin. Theory Ser. B 86 (2002) 135–147.
[12] T. Böhme, B. Mohar and C. Thomassen, Long cycles in graphs on a ﬁxed surface, J.
Combin. Theory Ser. B 85 (2002) 338–347.
[13] G. Brinkmann, J. Souﬀriau and N. Van Cleemput, On the strongest form of a theoremof Whitney for Hamiltonian cycles in plane triangulations, J. Graph Theory 83 (2016)
78–91.
15[14] G. Brinkmann and C.T. Zamﬁrescu, Polyhedra with few 3-cuts are hamiltonian, preprint(2018) https://arxiv.org/abs/1606.01693[15] Broersma, On some intriguing problems in hamiltonian graph theory – a survey, Discrete
Math. 251 (2002) 47–69.
[16] R. Brunet, M.N. Ellingham, Z. Gao, A. Metzlar and R.B. Richter, Spanning planar
subgraphs of graphs on the torus and Klein bottle, J. Combin. Theory Ser. B 65 (1995)
7–22.
[17] R. Brunet, A. Nakamoto and S. Negami, Every 5-connected triangulation of the Kleinbottle is Hamiltonian, Yokohama Math. J. 47 (1999) 239–244.
[18] R. Brunet and R.B. Richter, Hamiltonicity of 5-connected toroidal triangulations,J. Graph Theory 20 (1995) 267–286.
[19] C. Chen, Any maximal planar graph with only one separating triangle is Hamiltonian,
J. Comb. Optim. 7 (2003) 79–86.
[20] G. Chen, Y. Egawa, K. Kawarabayashi, B. Mohar and K. Ota, Toughness of Ka,t -minorfree graphs, Electron. J. Combin. 18 (2011) # P148.
[21] G. Chen, G. Fan and X. Yu, Cycles in 4-connected planar graphs, European J. Combin. 25 (2004) 763–780.
[22] G. Chen, L. Sheppardson, X. Yu and W. Zang, The circumference of a graph with noK3,t -minor, J. Combin. Theory Ser. B 96 (2006) 822–845.
[23] N. Chiba and T. Nishizeki, A theorem on paths in planar graphs, J. Graph Theory 10(1986) 449–450.
[24] N. Chiba and T. Nishizeki, The Hamiltonian cycle problem is linear-time solvable for
4-connected planar graphs, J. Algorithms 10 (1989) 187–211.
[25] M. Chudnovsky, B. Reed and P. Seymour, The edge-density for K2,t minors, J. Combin. Theory Ser. B 101 (2011) 18–46.
[26] V. Chvátal, Tough graphs and hamiltonian circuits, Discrete Math. 5 (1973) 215–228.
[27] V. Chvátal, Tough graphs and hamiltonian circuits, Discrete Math. 306 (2006) 910–917.
[28] Q. Cui, A note on circuit graphs, Electronic J. Discrete Math. 17 (2010) # N10.
[29] N. Dean, Lecture at Twenty-First Southeastern Conference on Combinatorics, Graph
Theory and Computing, Boca Raton, Florida, February 1990.
[30] M.B. Dillencourt, Hamiltonian cycles in planar triangulations with no separating triangles, J. Graph Theory 14 (1990) 31–39.
[31] G. Ding, Graphs without large K2 , n-minors, preprint (2020)
abs/1702.01355

https://arxiv.org/[32] M.N. Ellingham, Spanning paths, cycles and walks for graphs on surfaces, Congr. Numer. 115 (1996) 55–90.

16

[33] M.N. Ellingham and Z. Gao, Spanning trees in locally planar triangulations, J. Combin.
Theory Ser. B 61 (1994) 178–198.
[34] M.N. Ellingham and K. Kawarabayashi, 2-Connected spanning subgraphs with low maximum degree in locally planar graphs, J. Combin. Theory Ser. B 97 (2007) 401–412.
[35] M.N. Ellingham, E.A. Marshall, K. Ozeki and S. Tsuchiya, A characterization of K2,4 minor-free graphs, SIAM J. Discrete Math. 30 (2016) 955–975.
[36] M.N. Ellingham, E.A. Marshall, K. Ozeki and S. Tsuchiya, Hamiltonicity of planargraphs with a forbidden minor J. Graph Theory 90 (2019) 459–483.
[37] M.N. Ellingham and X. Zha, Toughness, trees, and walks, J. Graph Theory 33 (2000)
125–137.
[38] H. Enomoto, B. Jackson, P. Katerinis and A. Saito, Toughness and the existence of
k-factors, J. Graph Theory 9 (1985) 87–95.
[39] H. Enomoto, T. Iida and K. Ota, Connected spanning subgraphs of 3-connected planargraphs, J. Combin. Theory Ser. B 68 (1996) 314–323.
[40] H. Fleischner, The prism of a 2-connected, planar, cubic graph is hamiltonian, Ann. Discrete Math. 41 (1989) 141–170.
[41] J. Fujisawa, A. Nakamoto and K. Ozeki, Hamiltonian cycles in bipartite toroidal graphswith a partite set of degree four vertices, J. Combin. Theory Ser. B 103 (2013) 46–60.
[42] Z. Gao, 2-connected coverings of bounded degree in 3-connected graphs, J. Graph Theory
20 (1995) 327–338.
[43] Z. Gao and R.B. Richter, 2-walks in circuit graphs, J. Combin. Theory Ser. B 62 (1994)
259–267.
[44] Z. Gao, R.B. Richter and X. Yu, 2-walks in 3-connected planar graphs, Australas. J. Combin. 11 (1995) 117–122.
[45] Z. Gao, R.B. Richter and X. Yu, Erratum to: 2-walks in 3-connected planar graphs,
Australas. J. Combin. 36 (2006) 315–316.
[46] Z. Gao and N.C. Wormald, Spanning eulerian subgraphs of bounded degree in triangulations, Graphs Combin. 10 (1994) 123–131.
[47] W. Goddard, M.D. Plummer and H.C. Swart, Maximum and minimum toughness ofgraphs of small genus, Discrete Math. 167/168 (1997) 329–339.
[48] P.R. Goodey and M. Rosenfeld, Hamiltonian circuits in prisms over certain simple 3polytopes, Discrete Math. 21 (1978) 229–235.
[49] D. Gouyou-Beauchamps, The Hamiltonian circuit problem is polynomial for 4-connectedplanar graphs, SIAM J. Comput. 11 (1982) 529–539.
[50] B. Grünbaum, Polytopes, graphs, and complexes, Bull. Amer. Math. Soc. 76 (1970)
1131–1201.
[51] J. Harant, Toughness and nonhamiltonicity of polyhedral graphs, Discrete Math. 113(1993) 249–253.
17

[52] M. Hasanvand, Spanning closed walks with bounded maximum degrees of graphs on
surfaces, preprint (2017) https://arxiv.org/abs/1712.00125[53] G. Helden, Each maximal planar graph with exactly two separating triangles is Hamiltonian, Discrete Appl. Math. 155 (2007) 1833–1836.
[54] B. Jackson and N.C. Wormald, k-walks of graphs, Australas. J. Combin. 2 (1990) 135–
146.
[55] B. Jackson and X. Yu, Hamilton cycles in plane triangulations, J. Graph Theory 41(2002) 138–150.
[56] H.A. Jung, On a class of posets and the corresponding comparability graphs, J. Combin.
Theory Ser. B 24 (1978) 125–133.
[57] T. Kaiser, Z. Ryjáček, D. Král’, M. Rosenfeld and H.-J. Voss, Hamilton cycles in prisms,
J. Graph Theory 56 (2007) 249–269.
[58] K. Kawarabayashi, A theorem on paths in locally planar triangulations, European J.
Combin. 25 (2004) 781–784.
[59] K. Kawarabayashi, A. Nakamoto and K. Ota, 2-connected 7-coverings of 3-connected
graphs on surfaces, J. Graph Theory 43 (2003) 26–36.
[60] K. Kawarabayashi, A. Nakamoto and K. Ota, Subgraphs of graphs on surfaces with highrepresentativity, J. Combin. Theory Ser. B 89 (2003) 207–229.
[61] K. Kawarabayashi and K. Ozeki, 4-connected projective-planar graphs are hamiltonianconnected, J. Combin. Theory Ser. B 112 (2015) 36–69.
[62] K. Kawarabayashi and K. Ozeki, 5-connected toroidal graphs are Hamiltonianconnected, SIAM J. Discrete Math. 30 (2016) 112–140.
[63] K. Kawarabayashi and K. Ozeki, Spanning closed walks and TSP in 3-connected planargraphs, J. Combin. Theory Ser. B 109 (2014) 1–33.
[64] X. Lu and D.B. West, A new proof that 4-connected planar graphs are Hamiltonianconnected, Discuss. Math. Graph Theory 36 (2016) 555–564.
[65] J. Malkevitch, Polytopal graphs, in Selected Topics in Graph Theory, vol. 3, Academic
Press, New York, (1988) 169–188.
[66] B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins Univ. Press, Baltimore, (2001).
[67] A. Nakamoto, Y. Oda and K. Ota, 3-trees with few vertices of degree 3 in circuit graphs,
Discrete Math. 309 (2009) 666–672.
[68] A. Nakamoto and K. Ozeki, Hamiltonian cycles in bipartite quadrangulations on thetorus, J. Graph Theory 69 (2012) 143–151.
[69] A. Nakamoto and K. Ozeki, Spanning trees with few leaves in graphs on surfaces, in
preparation.
[70] C.St.J.A. Nash-Williams, Unexplored and semi-explored territories in graph theory, in“New directions in the theory of graphs”, Academic Press, New York, (1973) 149–186.
18

[71] T. Nishizeki, A 1-tough nonhamiltonian maximal planar graph, Discrete Math. 30 (1980)
305–307.
[72] T. Nishizeki and N. Chiba, Planar Graphs: Theory and Algorithms, Annals of Discrete
Mathematics 32 North-Holland, Amsterdam, 1988.
[73] K. Ota and K. Ozeki, Spanning trees in 3-connected K3,t -minor-free graphs, J. Combin. Theory Ser. B 102 (2012) 1179–1188.
[74] P.J. Owens, Non-hamiltonian maximal planar graphs with high toughness, Tatra
Mt. Math. Publ. 18 (1999) 89–103.
[75] K. Ozeki, A shorter proof of Thomassen’s theorem on Tutte paths in plane graphs, SUT
J. Math. 50 (2014) 417–425.
[76] K. Ozeki, A spanning tree with bounded maximum degrees of graphs on surfaces, SIAM
J. Discrete Math. 27 (2013) 422–435.
[77] K. Ozeki, N. Van Cleemput, C.T. Zamﬁrescu, Hamiltonian properties of polyhedra withfew 3-cuts - A survey, Discrete Math. 341 (2018) 2646–2660.
[78] K. Ozeki and P. Vràna, 2-edge-Hamiltonian connectedness of planar graphs, Europe
J. Combin. 35 (2014) 432–448.
[79] K. Ozeki and T. Yamashita, Spanning trees – a survey, Graphs Combin. 27 (2011) 1–26.
[80] K. Ozeki and C.T. Zamﬁrescu, Every 4-connected graph with crossing number 2 ishamiltonian, SIAM J. Discrete Math. 32 (2018) 2783–2794.
[81] P. Paulraja, A characterization of hamiltonian prisms, J. Graph Theory 17 (1993) 161–
171.
[82] M.D. Plummer, Problem in inﬁnite and ﬁnite sets, in “Colloquia Mathematica SocietatisJános Bolyai 10” 1549–1559, North-Holland, Amsterdam (1975).
[83] G. Ringel, Das Geschlecht des vollständigen paaren Graphen, Abh. Math. Sem. Univ.
Hamburg 28 (1965) 139–150.
[84] G. Ringel, Der vollständige paare Graph auf nichtorientierbaren Flächen, J. Reine
Angew. Math. 220 (1965) 88–93.
[85] M. Rosenfeld, On spanning subgraphs of 4-connected planar graphs, Graphs Combin. 25(1989) 279–287.
[86] M. Rosenfeld and D. Barnette, Hamiltonian circuits in certain prisms, Discrete Math. 5(1973) 389–394.
[87] D.P. Sanders, On hamilton cycles in certain planar graphs, J. Graph Theory 21 (1996)
43–50.
[88] D.P. Sanders, On paths in planar graphs, J. Graph Theory 24 (1997) 341–345.
[89] D.P. Sanders and Y. Zhao, On 2-connected spanning subgraphs with low maximum
degree, J. Combin. Theory Ser. B 74 (1998) 64–86.

19

[90] D.P. Sanders and Y. Zhao, On spanning trees and walks of low maximum degree,
J. Graph Theory 36 (2001) 67–74.
[91] E.F. Schmeichel and G.S. Bloom, Connectivity, genus, and the number of components
in vertex-deleted subgraphs, J. Combin. Theory Ser. B 27 (1979) 198–201.
[92] A. Schmid and J.M. Schmidt, Computing 2-walks in polynomial time, ACM Trans. Algorithms, 14 (2018) Art. 22, 18 pp.
[93] A. Schmid and J.M. Schmidt, Computing Tutte paths, preprint (2017)arxiv.org/abs/1707.05994

https://[94] S. Spacapan, A counterexample to prism-hamiltonicity of 3-connected planar graphs,
preprint (2019) https://arxiv.org/abs/1906.06683[95] P.G. Tait, Remarks on the colouring of maps, Proc. Roya; Soc. London 10 (1880) 729.
[96] R. Thomas and X. Yu, 4-connected projective-planar graphs are Hamiltonian, J. Combin. Theory Ser. B 62 (1994) 114–132.
[97] R. Thomas and X. Yu, Five-connected toroidal graphs are hamiltonian, J. Combin.
Theory Ser. B 69 (1997) 79–96.
[98] R. Thomas, X. Yu and W. Zang, Hamilton paths in toroidal graphs, J. Combin. Theory
Ser. B 94 (2005) 214–236.
[99] C. Thomassen, A theorem on paths in planar graphs, J. Graph Theory 7 (1983) 169–176.
[100] C. Thomassen, Trees in triangulations, J. Combin. Theory Ser. B 60 (1994) 56–62.
[101] W.T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956) 99–116.
[102] W.T. Tutte, Bridges and Hamiltonian circuits in planar graphs, Aequationes Math. 15(1977) 1–33.
[103] W.T. Tutte, On hamiltonian circuits, J. London Math. Soc. 2 (1946) 98–101.
[104] X. Yu, Disjoint paths, planarizing cycles, and spanning walks, Trans. Amer.
Math. Soc. 349 (1997) 1333–1358.
[105] H. Whitney, A theorem on graphs, Ann. of Math. 32 (1931) 378–390.
[106] S. Win, On a connection between the existence of k-trees and the toughness of a graph,
Graphs Combin. 5 (1989) 201–205.

20