ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 17 (2019) 51-66
https://doi.org/10.26493/1855-3974.1733.8c6
(Also available at http://amc-journal.eu)
Types of triangle in plane Hamiltonian triangulations and applications to domination
and k-walks
Gunnar Brinkmann
Ghent University, TWIST, Krijgslaan 281 S9, B9000 Ghent, Belgium
Kenta Ozeki
Yokohama National University, 79-2 Tokiwadai Hodogaya-ku, Yokohama 240-8501, Japan
Nico Van Cleemput
Ghent University, TWIST, Krijgslaan 281 S9, B9000 Ghent, Belgium
Received 19 June 2018, accepted 29 January 2019, published online 19 June 2019
We investigate the minimum number t0(G) of faces in a Hamiltonian triangulation G so that any Hamiltonian cycle C of G has at least t0(G) faces that do not contain an edge of C. We prove upper and lower bounds on the maximum of these numbers for all triangulations with a fixed number of facial triangles. Such triangles play an important role when Hamiltonian cycles in triangulations with 3-cuts are constructed from smaller Hamiltonian cycles of 4-connected subgraphs. We also present results linking the number of these triangles to the length of 3-walks in a class of triangulation and to the domination number.
Keywords: Graph, Hamiltonian cycle, domination, 3-walk. Math. Subj. Class.: 05C45, 05C10, 05C38
1 Introduction
In this article all triangulations are simple triangulations of the plane with at least 4 vertices. A triangulation or a graph is said to be Hamiltonian if it contains a Hamiltonian cycle. For a triangulation G with a Hamiltonian cycle C of G, a type-i triangle with i G {0,1, 2} is defined as a facial triangle of G which shares exactly i edges with C. We define U(G, C)
E-mail addresses: gunnar.brinkmann@ugent.be (Gunnar Brinkmann), ozeki-kenta-xr@ynu.ac.jp (Kenta Ozeki), nico.vancleemput@gmail.com (Nico Van Cleemput)
Abstract
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
38
ArsMath. Contemp. 17 (2019) 51-49
as the number of type-« triangles. If the triangulation and Hamiltonian cycle are clear from the context, we will also just write tj.
A triangulation G can be extended by inserting a 4-connected triangulation or polyhedron in a triangle T to obtain a larger graph G'. If there is a Hamiltonian cycle C in G, then we can extend C to a Hamiltonian cycle of G' - unless T is a type-0 triangle. If there is a Hamiltonian cycle C without any type-0 triangles such as in a double wheel or the majority of small 4-connected triangulations (e.g. more than 80% for 4-connected triangulations on 20 vertices), then for the graph G' obtained by inserting a 4-connected triangulation or polyhedron in each triangle in a set of disjoint facial triangles we can extend C to a Hamiltonian cycle of G'. In [3] it is proven that the - still open - question whether all triangulations with at most four 3-cuts are Hamiltonian can be reduced to the question whether for each set of four disjoint triangles in a 4-connected triangulation there is a Hamiltonian cycle so that none of them is a type-0 triangle. More properties of triangulations with a Hamiltonian cycle with few or even without type-0 triangles are described in Section 4. Investigating whether there always exists a Hamiltonian cycle with few type-0 triangles is the main target of this paper.
We denote the number of facial triangles of G by t(G). Euler's formula implies that (with |G| the number of vertices of G), t(G) = 2|G| - 4, so it is always an even number. For i G {0,2} we further define
and for even t > 4
tj(t) = max{tj(G) | G is a Hamiltonian triangulation with exactly t facial triangles}.
In some cases we might want to restrict the class to 4- or 5-connected triangulations. Note that there are no 4-connected triangulations G with t(G) < 8 and no 5-connected triangulations G with t(G) < 20. So for j = 4 and even t > 8, and for j = 5 and even t > 20 we define
tj (t) = max{tj(G) | G is a j -connected triangulation with exactly t facial triangles}. In this paper, we show the following theorem.
Theorem 1.1. Let t be an integer. Then the following hold.
(i)	For t > 8 we have t0(t) < , and for 4 < t < 8 we have t0(t) = 0.
(ii)	For t > 10 we have t4(t) < , and for t = 8 we have t0(t) = 0.
(iii)	For t > 20 we have t0(t) < 1-12.
In Section 3, we discuss lower bounds on t0(t), t$(t) and t§(t). As we will see in Section 4.1, also the number of type-i triangles on one side of a Hamiltonian cycle is relevant, so we also define tj(G, C) as the number of type-i triangles on that side of C with fewer type-i triangles. The numbers tj(G), tj(t), and tj (t) are defined correspondingly. By definition
tj(G) = min{tj(G, C) | C is a Hamiltonian cycle of G},
tj(G, C) < tj(G, C)/2, ti(t) < tj(t)/2 and
ti(G) < tj(G)/2, tj (t) < tj (t)/2
G. Brinkmann et al.: Types of triangle in plane Hamiltonian triangulations and applications .
53
for i e {0, 2} and j e {4,5}.
An outer plane graph is a plane graph in which all vertices are incident with the outer face. In particular, an outer plane graph with maximal number of edges is called a maximal outer plane graph, which is, in other words, an outer plane graph in which all inner faces are triangles. For a triangulation G with a Hamiltonian cycle C, the inside as well as the outside of C together with C form a maximal outer plane graph. For a 2-connected plane graph G, the boundary of the outer face is called the boundary cycle of G. In particular, vertices and edges in the boundary cycle of G are boundary vertices resp. boundary edges in G. A cycle C in a plane graph such that the inside as well as the outside (not including C) contain a vertex is called a separating cycle. Note that in a triangulation, any triangle that is not facial is a separating cycle.
Let G be a triangulation with a Hamiltonian cycle C. If we take the dual of the maximal outer plane graph consisting of the inside of C together with C and delete the vertex corresponding to the outer face, then we obtain a subcubic tree in which the vertices of degree (3 - i) correspond to type-i triangles of the triangulation. Using these relations, we get the following proposition.
Proposition 1.2. Let G be a triangulation with a Hamiltonian cycle C. Then i2(G,C )= to(G,C ) + 2 and i2(G,C)= to(G,C)+4.
Note that the number of facial triangles on the inside is equal to the number of facial triangles on the outside. As t(G) = t0(G, C) + ti(G, C) + t2(G, C), we have
ti(G, C) = t(G) - 2t0(G, C) - 4.
So finding the minimum value for t0 (G, C) is equivalent to finding the minimum value for t2(G, C), and finding the maximum value for t1(G, C).
Let G be a triangulation and let C be a Hamiltonian cycle in G. We say that two facial triangles are adjacent if they share an edge. An (i,j)-pair (i, j e {1,2}) is defined as a pair of adjacent facial triangles consisting of a type-i triangle and a type-j triangle such that the common edge is contained in C. Note that each type-1 triangle is contained in at most one (1, 2)-pair.
2 Upper bounds for t0(t), t^(t) and t0(t)
To prove Theorem 1.1 in this section, we first show some lemmas. A vertex v in a graph G is said to be dominating if v is adjacent to all other vertices in G.
If a type-2 triangle T is contained in two (2,2)-pairs, we call the three triangles involved a (2,2,2)-triple and T the central triangle of the triple.
Restricted to minimum degree 4 the first part of the following lemma was proven in [13, Lemma 2.1].
Lemma 2.1. Let G be a triangulation with a Hamiltonian cycle C, but without a dominating vertex. Then there exists a Hamiltonian cycle C' in G such that C' has no (2, 2,2)-triples.
If G has minimum degree 4, then C' can be chosen in a way that it also has at least as many (1,1)-pairs as C.
38
104	ArsMath. Contemp. 17 (2019) 54-114
Proof. Assume that there is a (2,2,2)-triple with central triangle T and let v denote the vertex contained in all three triangles involved. As v is not dominating, there is a first vertex v0 in counterclockwise orientation from T around v that has a neighbour on C that is not a neighbour of v. Numbering the neighbours of v in clockwise orientation around v as v0, vi,..., vdeg(.y)_i, there is also a first vertex vk with k > 0 and a neighbour on C that is not a neighbour of v. We can reroute the part of C containing v, v0,..., vk along the path v0, v1,..., vk_1, v, vk. This operation is displayed in Figure 1. Of course the roles of v0 and vk are symmetric and we could do the same with their roles interchanged.
Figure 1: Rerouting a Hamiltonian cycle to remove a (2,2, 2)-triple.
If all vertices have degree at least 4, any new type-2 triangle contains v and the number of (2,2, 2)-triples is decreased. Furthermore, no (1,1)-pairs without a triangle containing v can be destroyed and after rerouting at least the edges v1v2, v2v3,..., vk_3vk_2 are common edges of a (1,1)-pair. These are k - 3 (1,1)-pairs, but note that k - 3 can be 0. Depending on whether v0v1 is the common edge of a (1,1)-pair in C, the triangles under discussion can belong to k - 3 or k - 4(1,1)-pairs before rerouting - so the number of (1,1)-pairs does not decrease.
The vertices v0 and vk always have degree at least 4, but if one of v1,..., vk_2 has degree 3, it is contained in a type-2 triangle not containing v. For v1,..., vk_3 (note that this set of vertices can be empty) this type-2 triangle has type-1 triangles on the other side of the edges in the Hamiltonian cycle and is therefore not contained in a (2,2)-pair. If vk_2 has degree 3 we would produce a (2, 2, 2)-triple. If v2 has degree larger than 3, we can apply the operation with the role of v0 and vk interchanged, so let us assume that v2 as well as vk_2 have degree 3. As no two vertices of degree 3 can be neighbours in a triangulation different from K4, this implies that k > 3.
Let i > 0 be minimal so that there is an edge vj vk_ 1. Such an i is sure to exist, as k - 3 is a candidate. We then reroute the cycle along v0, v1,..., vj, vk_1, vk_2,..., vi+1, v, vk to obtain C'. An example of this rerouting is given in Figure 2.
After rerouting, the only edges that can be the common edge of the two triangles in a new (2,2)-pair are vi+1 vi+2 and v4vk_1. As v^v^ is not in C for any i < j < k - 1, vjvk_1 can only be in a (2, 2)-pair if vk_1vk_2 is contained in the same trian^^ which gives i = k - 3, so vi+1vi+2 = vk_2vk_1 is the common edge of a (2,2)-pair too and only the case that vi+1 vi+2 is the common edge of a (2, 2)-pair remains to be discussed.
Assume that vi+2 vi+1 is contained in two type-2 triangles — vi+2vi+1v and T'. If the degree of vi+2 is 3, then T' = vi+1 vi+2 vi+3 and the second neighbour triangle of T' along C' is a type-1 triangle, so in that case vi+2vi+1 is not part of a (2, 2,2)-triple.
G. Brinkmann et al.: Types of triangle in plane Hamiltonian triangulations and applications ... 55
Figure 2: Rerouting a Hamiltonian cycle to remove a (2,2,2)-triple if vk-2 has degree 3.
If the degree of vi+2 is at least 4, the other edge of T' in the Hamiltonian cycle must be vi+2vj, which can only be contained in a type-2 triangle vi+2vi+1vj if i + 2 = k - 1, that is i = k - 3. In order to be contained in a second type-2 triangle, there must be an edge vfe-1vfc-4. Due to the minimality of i we get k = 4, so we have the situation depicted in Figure 3 on the left hand side. Rerouting the Hamiltonian cycle along v0, v, v2, v1, v3, v4 (right hand side of Figure 3) gives a Hamiltonian cycle with one (2, 2, 2)-triple less. □
Figure 3: Rerouting a Hamiltonian cycle to remove a (2, 2, 2)-triple if vk-2 has degree 3 and the default method produces a (2, 2,2)-triple.
Using a result by Whitney [17], we can prove the existence of a Hamiltonian cycle with at least one (1,1)-pair in a 4-connected triangulation. Below we first give the lemma by Whitney, but use a simplified version of the formulation from [7].
Lemma 2.2. Let G be a 4-connected triangulation. Consider a cycle D in G together with the vertices and edges on one side of D (referred to as the outside of D). Let a and b be two vertices of D dividing D into two paths Pi and P2 each of which contains both a and
'k-i
b.If
no two vertices of Pi are joined by an edge which lies outside of D and
104
ArsMath. Contemp. 17 (2019) 56-114
• there is a vertex z (distinct from a and b) dividing P2 into two paths P3 and P4 each of which contains z such that no pair of vertices in P3 and no pair of vertices in P4 are joined by an edge which lies outside of D,
then there is a path from a to b using only edges on and outside of D which passes through every vertex on and outside of D.
Using this lemma, we can give the following result. Note that for triangulations being k-connected is equivalent to having no separating cycles of length shorter than k.
Lemma 2.3. Let G be a 4-connected triangulation which is not isomorphic to the octahedron. There exists a Hamiltonian cycle C in G such that C has at least one (1,1)-pair.
ui
v
n
z
u
a
x
Figure 4: Construction of a Hamiltonian cycle with at least one (1,1)-pair in a 4-connected triangulation.
Proof. As a consequence of the Euler formula and the fact that G is not isomorphic to the octahedron, there exists a vertex x of degree at least 5 in G. Let uvx be an arbitrary triangle containing x. The edge uv is contained in a second triangle, say uvz. Let the vertices adjacent to u (in counterclockwise order) be v, z,ui,..., um, a, x (note that there are no Ui vertices if u has degree 4), and let the vertices adjacent to v be u,x,b,vi,..., vn, z (note that there are no vi vertices if v has degree 4) (see Figure 4).
As G is 4-connected, D = axbvi • • • vnzui • • • uma is a cycle in G. The vertices a and b partition D into two paths satisfying the conditions of Lemma 2.2 with Pi = axb. Indeed, the path P2 is divided into P3 and P4 by the vertex z. As x has degree at least 5, a and b are not adjacent. All vertices of P3, resp. P4, are adjacent to u, resp. v, so any edge which lies outside of D and joins two vertices of P3 or two vertices of P4 would be part of a separating triangle.
Let P be the path from a to b described in Lemma 2.2. The Hamiltonian cycle C = P U auvb contains the (1,1)-pair (uvx, uvz).	□
In the case of 5-connected triangulations, we can prove a slightly stronger result.
Lemma 2.4. Let G be a 5-connected triangulation. There exists a Hamiltonian cycle C in G such that C has at least two (1,1)-pairs.
G. Brinkmann et al.: Types of triangle in plane Hamiltonian triangulations and applications ... 57
Figure 5: Construction of a Hamiltonian cycle with at least two (1,1)-pairs in a 5-connected triangulation.
Proof. Let v be a vertex of G which has degree 5, and let u and w be two neighbouring vertices of v which are not adjacent to each other. Let the vertices adjacent to u be
v, z, ui,..., um, a, x, and let the vertices adjacent to w be v, y, b, w^ ..., wn, z (see Figure 5).
As G is 5-connected, D = axybw1 • • • wnzu1 • • • uma is a cycle in G. The vertices a and b partition D into two paths satisfying the conditions of Lemma 2.2 with P1 = axyb. Indeed, the path P2 is divided into P3 and P4 by the vertex z. As all vertices have degree at least 5, any edge outside of D connecting two vertices of P1 is contained in a separating triangle or a separating quadrangle. All vertices of P3, resp. P4, are adjacent to u, resp. w, so any edge which lies outside of D and joins two vertices of P3 or P4 would be part of a separating triangle.
Let P be the path from a to b described in Lemma 2.2. The Hamiltonian cycle C = P U auvwb contains the (1,1)-pairs (uvx, uvz) and (vwy, vwz).	□
Lemma 2.5. Let G be a triangulation with a dominating vertex v and t triangles. Then t0(G) < 4 - 1 if G is not K4 and t0(K4) = 0.
Proof. We can easily check K4 by hand, so assume that G is not K4.
G - {v} is an outer plane graph, so it has a vertex w of degree 2. Let w' be a vertex sharing a boundary edge of G - {v} with w and let C be the Hamiltonian cycle of G containing {v, w}, {v, w'} and the boundary cycle of G - {v} without the edge {w, w'}. Let t0,A, t1jA and t2,A be the number of facial triangles of type 0, 1 and 2 on the side of C containing the triangle v, w, w'. All triangles on the other side of C contain v and as no type-0 triangle in G contains v, we have t0(G) = t0,A. Since each side of C contains exactly t(G)/2 facial triangles, we have t0,A + t1jA + t2,A = . Furthermore (as G is not K4) we have t1jA > 1 (the unique triangle containing w but not v). So t0,A + t2,A < t0,A + t1jA + t2,A = 2. By Proposition 1.2, we have t2,A = t0,A + 2, and hence we get 2t0,A + 2 = 2t0 + 2 <2 and finally t0(G) < 4 - 1. ' '	□
By combining the results above, we are now ready to prove Theorem 1.1.
u
y
x
Proof of Theorem 1.1. For t < 20 the theorem was checked by testing all triangulations. The triangulations were generated by the program plantri [2] and a straightforward exhaustive search for Hamiltonian cycles with the smallest number of type-0 triangles was
104
ArsMath. Contemp. 17 (2019) 58-114
performed. Thus, we may assume t > 20. Let G be a Hamiltonian triangulation with t > 20 facial triangles.
Suppose that G has a dominating vertex v. Since G - {v} has a vertex of degree two, G has a 3-cut, and hence G is not 4-connected. Since 4 - 1 < i-8, Lemma 2.5 implies the result.
Assume now that G has no dominating vertex. Suppose that G has a Hamiltonian cycle with p (1,1)-pairs. Lemmas 2.3 and 2.4 imply that p > 1 if G is 4-connected, and p > 2 if G is 5-connected. Due to Lemma 2.1, G contains a Hamiltonian cycle C' which has at least p (1,1)-pairs and in which each type-2 triangle is contained in at least one (1, 2)-pair. A type-1 triangle is contained in a (1,1)-pair or a (1,2)-pair. There are at least 2p type-1 triangles in (1,1)-pairs of C' and therefore at most (ti(G, C') - 2p) type-1 triangles in (1,2)-pairs. Since each type-2 triangle forms a (1, 2)-pair with at least one of the type-1 triangles in a (1,2)-pair, we get
t2(G,C') < ti(G,C') - 2p. By Proposition 1.2, we have t2 (G, C') = t0(G, C') + 4, and hence
ti(G,C') > to(G,C') + 4 + 2p.
Combining these results with t(G) = t0(G, C') + t1(G, C') + t2(G, C'), we get t(G) > to(G, C') + to(G, C') + 4 + 2p + to(G, C') + 4.
This can be rewritten as
and so we also have
to(G,C') < t(G) - 8 - 2p
to(t) <
3
t - 8 - 2p
3
Using the values for p from Lemma 2.3 and Lemma 2.4, we get the given bounds. □
3 Lower bounds for t0 (t), t^ (t) and t^ (t)
In order to prove lower bounds for to(t), to(t) and t§(t), we will construct families of graphs in which each Hamiltonian cycle has at least a certain number of type-0 triangles.
Theorem 3.1.
•	Let t > 16 be even. Then to(t) > L|J - 5 and to(t) > L^J - 3.
We have to(14) = 1 and io(14) = 0. For t < 14 we have to(t) = io(t) = 0.
•	Let t > 18 be even. Then t4(t) > 2(L6J - 3) and i4(t) > L6J - 3. For t < 18 we have t4(t) =o ¿4(t) = 0.
•	Let t > 20 be even. Then ig(t) > 2L 1t2J - 20. For t < 66 we have that tg(t) = 0.
Proof. t4(t) and ¿¡0(t):
The results for t < 18 were determined by a computer using the program plantri [2] for the generation of all 4-connected triangulations and a straightforward algorithm to compute to and t o.
G. Brinkmann et al.: Types of triangle in plane Hamiltonian triangulations and applications ... 
59
First consider the case where t is a multiple of six, and let k = |. Consider the fragment B shown in the left part of Figure 6. Take k copies Bo,..., Bfc_i of B and identify all vertices labelled N and all vertices labelled S, respectively, (we call the resulting vertices the poles) and for 0 < i < k identify vertex y in Bj with vertex x in Bi+1 (mod k). This graph has 6k facial triangles, and we denote it by Gk. It is easy to check that Gk is 4-connected.
N
N
Figure 6: The fragment B used to construct a family of triangulations establishing a lower bound on t0 (t) and t0 (t) and the most common way for a Hamiltonian cycle to pass through this fragment.
We show t0 (Gk) > 2( | - 3) and i0 (Gk, C) > | - 3 by induction on k. Computational results give that for 3 < k < 8 we have t0(Gk) = 2k - 6 and t0(Gfc) = k - 3. Since Gk contains 6k triangles, we can also write this as t0(Gk) = | - 6 and i0(Gfc) = t - 3, and we are done. So we may assume that k > 9.
Let C be a Hamiltonian cycle in Gk. An edge of C which is incident to a pole is contained in at most two fragments. Since there are two edges incident to each pole, there are at most 8 fragments that contain an edge of C that is incident to a pole. Since k > 9, we may assume that C visits the fragment Bk-1 - up to symmetry - as shown in the right part of Figure 6. This part of the Hamiltonian cycle C produces two type-0 triangles in Bk-1 -one on each side of C. So, by removing two inner vertices of Bk-1, identifying the vertex y in the copy Bk_2 and the vertex x in the copy B0, we obtain a Hamiltonian cycle, say C', in Gfc_i. By the induction hypothesis, t0(Gfc_i, C) > 2( t_6 - 3) and i0(Gfc_i, C') > i-6 - 3. Since t0(Gfc, C) = t0(Gfc_i, C') + 2 and t_0(Gfc, C) = t_0(Gfc_i, C') + 1, we obtain the desired inequality.
For the case where t is not a multiple of six, we let k = [|J. We apply the same construction, but for a pair of neighbouring fragments we connect the x- and y-vertex by an edge instead of identifying them - see the left part of Figure 7 - or with an extra vertex of degree 4 that is also connected to the poles. This gives 2, resp. 4 extra triangles. Confirming the formulas for these modified triangulations with 3 to 8 fragments with a computer, one can apply the same argumentation as above to prove the equations in the lemma.
to(t) and to (t):
For t0(t) and t0(t), where 3-cuts are allowed, we use the same fragment and the same constructions as for t0(t) and t0(t), but for two fragments we do not identify x and y but instead connect N and S by an edge between these segments - see the right part of Figure 7.
y
x
S
S
104	ArsMath. Contemp. 17 (2019) 60-114
of 6 and for the 3-connected case.
This construction with k fragments gives triangulations with 6k + 2 facial triangles that can be extended to triangulations with 6k + 4 and 6(k + 1) facial triangles by inserting vertices of degree 3 in one or both triangles containing the edge between the poles.
Computational results for k < 8 fragments combined with the same reduction argument as before give that t0(t) > L3J - 5 and i0(t) > LJ - 3.
Remark. For small values of t a double wheel where triangles are subdivided with a vertex of degree 3 alternatingly on both sides of the rim gives a larger result for t0(t) and i0(t), but the linear factor is only 4, so that the advantage compared to the sequence described is only for small values.
t0(t) and t0(t):
For t < 130 we have that t0(t) > 0 > 2L^J - 20. So assume that t is even and t > 130.
For even t > 130 we can construct triangulations in a similar way as for the cases t4(t) and t"o(t), but use the fragments depicted in Figure 8. We use r = (t - 12L12J)/2 copies B'0,..., of the right fragment with 14 triangles and l = L12 J - r copies Br,..., B'rof the left fragment with 12 triangles.
We identify all vertices labelled N and all vertices labelled S, respectively, and for 0 < i < r + l identify the vertices y, y' in B'i with the vertices x, x' in Bi+1 (mod (r+l)) respectively. It is easy to check that the resulting graph Grjl is 5-connected.
Checking the different ways how a Hamiltonian cycle can pass the left fragment in Figure 8 without using the poles and saturate the 4 interior vertices (some boundary vertices can also be saturated from outside the segment), gives that each such segment contains at least 2 type-2 triangles. As the fragment on the right hand side of Figure 8 contains the one on the left hand side, the same is true for the fragment on the right hand side too.
So for t > 130 and consequently r+l > 11 any Hamiltonian cycle C in Gr l has at least r+1 - 8 fragments not containing an edge of C incident with a pole and therefore containing at least 2 type-2 triangles. So t2(Gr,i, C) > 2(r + l - 8) and therefore t0(Gr,i, C) > 2(r + l - 8) - 4 = 2(r + l) - 20. As r + l = L12J we get tg(t) > 2Ll2J - 20. '
The result for to(t) was proven by a computer search testing graphs constructed by the program plantri [2]. All 5-connected triangulations G with up to 66 triangles were found to have i0(G) = 0. It should also be noted that the graphs Gr l constructed for the first part all allow a Hamiltonian cycle C with i0(G, C) = 0.	□
G. Brinkmann et al.: Types of triangle in plane Hamiltonian triangulations and applications ... 
61
Figure 8: The fragments used for the 5-connected case.
Computational results for r = 0 and l < 8 suggest that t0 (t) > 2 [ 12 J - 8, but a proof similar to the one for t0 (t) and t0 (t) is out of reach on the computational side for the basic step in the induction and would be very lengthy on the theoretical side.
For t0(t), i0(t), t0(t), and ¿0(t) the upper and lower bounds differ only by an additive constant, so there is not much room for improvement. For t5(t), and especially ig(t) the upper and lower bounds are far apart and have a different growth rate. In these cases there is not only room, but also need for improvement.
4 Applications different from Hamiltonian cycles
Type-0 triangles are of their own interest in the context of Hamiltonicity of triangulations, as they are the problematic case for the extendability of partial Hamiltonian cycles to the inside of separating triangles (see e.g. [9]), but the number t0(G) has also an impact on invariants that are not that obviously related to Hamiltonian cycles. In this section, we describe two other topics in graph theory for which the value of t0 (G) is relevant.
4.1 The domination number of a triangulation
A vertex subset S of a graph G is said to be dominating if every vertex in G - S has a neighbour in S. The cardinality of a minimum dominating set of G is called the domination number of G and is denoted by 7(G). For a triangulation G, Matheson and Tarjan [11] proved that 7(G) < ^ and they conjectured that 7(G) < . This conjecture is still open, even when restricted to 4- or 5-connected triangulations.
Plummer, Ye and Zha [13] proved that 7(G) < min {[^y^l, L^ilFJ} for any 4-connected triangulation G. This is the currently best approach towards the Matheson-Tarjan conjecture. The idea of their inductive proof is to find a Hamiltonian cycle with certain properties of type-2 triangles and to use these for reduction of the graph.
If we can find a Hamiltonian cycle with few type-2 triangles, then (as implicitly used in [13]) we can bound the size of a dominating set as follows: Let C be a Hamiltonian cycle. By symmetry we can assume that the number of type-2 triangles on the inside of C is less than or equal to that on the outside of C. Let G' be the maximal outer plane graph consisting of the inside of C together with C. Note that G' contains i2(G, C) type-2 triangles. It is shown in [5, 16] that any maximal outer plane graph H satisfies 7(H) < lgl+4fc(g-1, where k(H) denotes the number of vertices of degree 2 in H. Any vertex of degree two in G' is the common end vertex of two edges of C in a type-2 triangle. Thus, we have
104
ArsMath. Contemp. 17 (2019) 62-114
k(G') = t2(G, C). Since t 2(G, C) = t o(G, C) + 2, we obtain by Proposition 1.2 |G| + k(G') |G| + Î2(G,C) _ |G| + to(G,C)+2
y(g) < y(g') < <
4	4
2|G| + to(G, C)+4 8 '
So for a given Hamiltonian triangulation, a Hamiltonian cycle C with few type-0 triangles possibly gives a good upper bound on the domination number in that triangulation. In general though, the impact of the values of t0(t) is a negative one: the lower bounds given in Theorem 3.1 show that at least for 4-connected triangulations a direct application of this method cannot lead to improved bounds for the domination number.
4.2 3-walks with few vertices visited more than once
A k-tree of a graph G is a spanning tree of G in which every vertex has degree at most k. A k-walk is a spanning closed walk that visits every vertex at most k times. It is well-known that a graph that contains a k-walk also contains a (k + 1)-tree, see [8] (but the converse does not hold in general). Furthermore, the vertices visited k times in a k-walk correspond to vertices of degree k + 1 in the (k + 1)-tree that is constructed.
Every 3-connected planar graph admits a 3-tree [1] and a 2-walk [6]. The result about 3-trees was strengthened in [12] where it is shown that every 3-connected planar graph G
i —i_7
admits a 3-tree with at mosti—3— vertices of degree 3.
As in the construction of 3-trees from 2-walks in [8], vertices visited twice in a 2-walk correspond to vertices of degree 3 in the 3-tree, it was natural to consider the following problem, which was already mentioned in [12].
Problem 4.1. Is there for every 3-connected planar graph G a 2-walk such that the number
—
of vertices visited twice is at mosti——1 - c for a constant c?
Note that for a 2-walk in a graph G, the number of vertices visited twice is at most t if and only if its length is at most |G| + t. With this formulation of the problem in mind, the result that every 3-connected planar graph G contains a spanning closed walk of length at most 4|—3-4 (proven in [10]) can be considered as a first step towards the solution of Problem 4.1. However, a spanning closed walk constructed in [10] may visit a vertex many times, so Problem 4.1 is still open.
In this section we describe a different step towards the solution of Problem 4.1, by limiting the number of times a vertex is visited to 3. The class for which the result is proven is a subclass of all triangulations, but in fact a class containing cases for which Problem 4.1 would hold with equality. Type-0 triangles play an important role in the construction of the walks.
In the language of [9] the triangulations in the class of graphs we will describe now are those triangulations where the so-called decomposition tree is a star. In order not to refer the reader to [9] and to fix notation, we will give an independent description of the class here. To simplify notation, we consider K4 also as a 4-connected graph in this section. Let K be the set of all graphs G that can be constructed as follows: Take any 4-connected triangulation H and let F be a subset of facial triangles of H. For each facial triangle f = xyz G F, take a 4-connected plane graph Gf (not necessarily a triangulation) where the outer face is a triangle and let xf ,yf and zf be the three boundary vertices of Gf. Then
4
G. Brinkmann et al.: Types of triangle in plane Hamiltonian triangulations and applications ... 
63
G is obtained from H by adding Gf inside f for f e F, so that x, y, z are identified with xf,yf,zf, respectively. Except for the case when G is a triangulation with exactly one separating triangle the graph H is uniquely defined for each G e K and we write H(G) for it. In the case of one separating triangle there are two possible candidates for H and H(G) denotes an arbitrary one of them.
For example, the face subdivision of a 4-connected triangulation H belongs to K. In the definition above, F is the set of all facial triangles of H and for any face f we have Gf ~ K4. As in [12, Section 2], the face subdivision of a 4-connected triangulation shows that we cannot decrease the coefficient 3 of |G| in Problem 4.1. So, in this sense, some graphs in K belong to the most difficult ones for Problem 4.1.
The following result shows that a Hamiltonian cycle C in a 4-connected triangulation T with small t0(T, C) can be used to construct a 3-walk of short length for the graphs G e K with H(G) = T. Using Theorem 1.1, in Corollary 4.3 we obtain a general upper bound depending only on the number of vertices in G.
Theorem 4.2. Let G e K be given and C a Hamiltonian cycle in H = H(G). We write t'0(H, C) (or short t'0) for the number of those type-0 triangles of H that are not faces in G. Then G contains a 3-walk of length at most 4|G|+to_4 which visits each vertex not in H exactly once.
Proof. Let F, H, and for each facial triangle f e F also Gf ,xf ,yf, and zf be as in the definition of K. We denote the length of a walk W by l(W), and let |R|_ = |R| - 3 for a plane graph R. With this notation we have |G| = |H| + ^f eF |Gf |_.
Claim 4.2.1. For a 4-connected plane graph R where the outer face is a triangle (including K4) with vertices x, y, z in the boundary and a,b e {x, y, z} (with possibly a = b), there is a (possibly closed) walk PR,a,b of length |R|_ + 1 from a to b in R visiting exactly all vertices in R except those in {x, y, z} \ {a, b} and visiting vertices not in the boundary exactly once.
Proof. The case G = K4 can be easily checked by hand, so assume that G is not K4.
If a = b (w.l.o.g. a = b = x) then according to [15, (3.4)] there exists a Hamiltonian cycle in G — {y,z}, which is a closed walk with the given properties starting and ending in a.
If a = b (w.l.o.g. a = x, b = y), due to [14, Corollary 2] there is a Hamiltonian cycle C in G through {a, z} and {b, z}. C — {{a, z}, {b, z}} is the walk Pa,a,b.	□
For a given cycle C with a fixed vertex c1 we define a linear order along one of the directions of C starting from c1 as c1 < c2 < • • • < cn. For each facial triangle f of H we fix the notation of xf ,yf, zf so that xf < yf < zf. With this notation we have:
Claim 4.2.2. For any two triangles f and f' that belong to the same side of C we have
yf = yf' ■
Proof. Assume xf < xf'. C is divided into three segments by the vertices xf,yf and zf and - as xf' ,yf' and z f' are all at least x f and smaller than cn, they occur in one of these segments in the order xf' ,yf' ,zf'. This implies that only x f' and zf' can be one of the end vertices of the segment and yf' is in fact different from each of xf ,yf and zf.	□
104
ArsMath. Contemp. 17 (2019) 64-114
We consider the following spanning subgraph HQ of the dual of H: The vertex set of HQ is the set of triangles of H, and two faces are adjacent in HQ if and only if they share an edge in C. Note that for i € {0,1,2}, a type-i triangle has degree exactly i in H*. In particular, each component of HQ is an isolated vertex, a path or a cycle. We can give an orientation to the edges of such a component P*, so that each vertex in P*, except for isolated vertices and one of the end vertices when P* is a path, has out-degree one. In cases where only one end vertex v of such a path P* belongs to F, we choose v to have out-degree one.
Recall that F is the set of facial triangles of H into which a graph was inserted. We can partition F into two sets F0 and Fi. We define for i € {0,1}:
F_ = {f € F | f has out-degree exactly i}.
With ti(H, C) (or short ti) for the number of those type-1 triangles of H that are no faces in G our construction gives |F0| < t0 + \.
Now we modify C using Claim 4.2.1 so that for each triangle f € F it visits each vertex inside G f exactly once:
•	Suppose that f € F0. Then we add the walk PGf ,yf ,yf to C. This increases the length of C by |Gf + 1.
•	Suppose that f € F1. Let f' be the out-neighbour of f, and let {a, b} be the edge in C that is shared by f and f'.
Then we replace {a, b} in C by PGf ,a,b. This increases the length of C by only |Gf | _ as one edge in C is also deleted.
The resulting walk C' is a 3-walk because, by Claim 4.2.2, the number of times a vertex is visited is increased by at most 1 for each side of C.
We will first give some equations we will use to compute the length of C'. For the given Hamiltonian cycle C we denote t0(H, C), t1(H, C) and t2(H, C), by t0,t1,t2, respectively.
As t0 + t1 + t2 = t(H) = 2|H| - 4 and t2 = t0 +4 (by Proposition 1.2), we get |H| =	+4 > 2t°+tl- + 4.
As in each face of F at least one vertex is inserted, we get |G| > |H| + t0 + t1. So together with the previous equation |G| > 4t°+3t' + 4 = 6t°+3tl +4 - t0 which can be
j-i , t', , |G| + t°_4
rewritten as t0 + i1 < 1 1 3 °— we get
l(C') = 1(C) + £ |Gf |_ + ^ (|Gf |_ + 1) = 1(C) + £ |Gf |_ + |Fo|
f	f £F°	f £F
= |H| + £ |Gf |_ + |Fo| = |G| + |Fo| < |G| +10 + f
f £F
<- + |G| + to - 4 = 4|G| + to - 4
< |G| + 3 = 3
This completes the proof of Theorem 4.2.	□
Using Theorem 1.1(ii) we obtain the following corollary.
G. Brinkmann et al.: Types of triangle in plane Hamiltonian triangulations and applications ... 
65
Corollary 4.3. Except for K4, any graph G G K contains a 3-walk of length at most
22|G| - 34 15 '
Proof. Applying the construction of a walk from Theorem 4.2, we get that any graph G G
221 gg |_34
K with K4 = H(G) is Hamiltonian, so we just have to check whether |G| < —G—, which is the case for all graphs except K4 itself (that is if F = 0).
Assume now that t(H(G)) = 8, so H(G) is the octahedron. If G is Hamiltonian, then there is a walk of length |G| < 221 34. Otherwise it follows directly from Theorem 16 in [4] that |F| > 4. As that result is still unpublished, one can alternatively use our construction of a walk from Theorem 4.2 together with Theorem 4.1 from [9] to obtain that |F| > 4. Furthermore one can easily find a Hamiltonian cycle with |F0| < 2. With v > 4 the number of vertices added inside a triangle of the octahedron, the construction gives a 3-walk with length at most 6 + v + 2 and 6 + v + 2 < 22(6+1v5i)-34 for v > 4. From now on assume that H(G) has at least 10 faces.
Let C be a Hamiltonian cycle in H = H(G) with t0(H) type-0 triangles. Let ¿0 denote the number of type-0 triangles of C in H that are not faces in G. As each triangle in F contains at least one vertex, we have that |G| > |H| + t0. By Theorem 1.1(ii), we get t4(t(H)) <	and
t0 < ^(H)) = t0(2|H|-4) < ffi^ < 2'|G|-;0' - 14 which implies
2|G| — 14
t0 < 5 '
Substituting this into the equation given in Theorem 4.2, we get Corollary 4.3.	□
5 Correctness of the computer programs used
The programs constructing Hamiltonian cycles and computing t0( ) and t0( ) are straightforward branch and bound programs that can be obtained from the authors or be downloaded from http://caagt.ugent.be/type0/ to check the source code, to check the computational results in this paper, or to be used otherwise. Two independent programs were developed and implemented and the results were compared for each of the around 150 000000 triangulations with up to 30 triangles generated by plantri. There was full agreement. The computation of t0( ) for 5-connected triangulations was done independently up to 60 triangles and for larger values only by the faster of the two programs.
References
[1]	D. Barnette, Trees in polyhedral graphs, Canad. J. Math. 18 (1966), 731-736, doi:10.4153/ cjm-1966-073-4.
[2]	G. Brinkmann and B. D. McKay, Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem. 58 (2007), 323-357, http://match.pmf.kg.ac.rs/electronic_ versions/Match58/n2/match58n2_323-357.pdf, see also http://cs.anu. edu.au/~bdm/index.html.
104	ArsMath. Contemp. 17 (2019) 66-114
[3]	G. Brinkmann, J. Souffriau and N. Van Cleemput, On the strongest form of a theorem of Whitney for Hamiltonian cycles in plane triangulations, J. Graph Theory 83 (2016), 78-91, doi: 10.1002/jgt.21915.
[4]	G. Brinkmann and C. T. Zamfirescu, Polyhedra with few 3-cuts are hamiltonian, Electron. J. Combin. 26 (2019), #P1.39 (16 pages), https://www.combinatorics.org/ojs/ index.php/eljc/article/view/v2 6i1p3 9.
[5]	C. N. Campos and Y. Wakabayashi, On dominating sets of maximal outerplanar graphs, Discrete Appl. Math. 161 (2013), 330-335, doi:10.1016/j.dam.2012.08.023.
[6]	Z. Gao and R. B. Richter, 2-walks in circuit graphs, J. Comb. Theory Ser. B 62 (1994), 259-267, doi:10.1006/jctb.1994.1068.
[7]	S. L. Hakimi, E. F. Schmeichel and C. Thomassen, On the number of Hamiltonian cycles in a maximal planar graph, J. Graph Theory 3 (1979), 365-370, doi:10.1002/jgt.3190030407.
[8]	B. Jackson and N. C. Wormald, k-walks of graphs, Australas. J. Combin. 2 (1990), 135-146, https://ajc.maths.uq.edu.au/pdf/2Zocr-ajc-v2-p135.pdf.
[9]	B. Jackson and X. Yu, Hamilton cycles in plane triangulations, J. Graph Theory 41 (2002), 138-150, doi:10.1002/jgt.10057.
[10]	K.-i. Kawarabayashi and K. Ozeki, Spanning closed walks and TSP in 3-connected planar graphs, J. Comb. Theory Ser. B 109 (2014), 1-33, doi:10.1016/j.jctb.2014.04.002.
[11]	L. R. Matheson and R. E. Tarjan, Dominating sets in planar graphs, European J. Combin. 17 (1996), 565-568, doi:10.1006/eujc.1996.0048.
[12]	A. Nakamoto, Y. Oda and K. Ota, 3-trees with few vertices of degree 3 in circuit graphs, Discrete Math 309 (2009), 666-672, doi:10.1016/j.disc.2008.01.002.
[13]	M. D. Plummer, D. Ye and X. Zha, Dominating plane triangulations, Discrete Appl. Math. 211 (2016), 175-182, doi:10.1016/j.dam.2016.04.011.
[14]	D. P. Sanders, On paths in planar graphs, J. Graph Theory 24 (1997), 341-345, doi:10.1002/ (sici)1097-0118(199704)24:4(341::aid-jgt6)3.0.co;2-o.
[15]	R. Thomas and X. Yu, 4-connected projective-planar graphs are Hamiltonian, J. Comb. Theory Ser.B 62 (1994), 114-132, doi:10.1006/jctb.1994.1058.
[16]	S.-i. Tokunaga, Dominating sets of maximal outerplanar graphs, Discrete Appl. Math. 161 (2013), 3097-3099, doi:10.1016/j.dam.2013.06.025.
[17]	H. Whitney, A theorem on graphs, Ann. of Math. 32 (1931), 378-390, doi:10.2307/1968197.