## HAMILTON CYCLES IN EMBEDDED GRAPHS

Roman Nedela and Martin ˇSkoviera University of West Bohemia, Pilsen

Comenius University, Bratislava

joint work with Michal Kotrbˇc´ık

SCDO 2016 Queenstown, New Zealand

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 1 / 32

## Lov´ asz problem

Problem (Lov´asz, 1969)

Does every vertex-transitive graphadmit a Hamilton path?

Conjecture (folklore)

Every Cayley graph(of order at least 3) has a Hamilton cycle.

Critical case: cubic Cayley graphs

## Lov´ asz problem

Problem (Lov´asz, 1969)

Does every vertex-transitive graphadmit a Hamilton path?

Conjecture (folklore)

Every Cayley graph(of order at least 3) has a Hamilton cycle.

Critical case: cubic Cayley graphs

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 2 / 32

## Lov´ asz problem

Problem (Lov´asz, 1969)

Does every vertex-transitive graphadmit a Hamilton path?

Conjecture (folklore)

Every Cayley graph(of order at least 3) has a Hamilton cycle.

Critical case: cubic Cayley graphs

## Hamilton cycles in cubic Cayley graphs

Theorem (Glover, Maruˇsiˇc, Kutnar, Malniˇc, 2007–2012)
Let K =Cay(H;r,r^{−1},l) be a cubic Cayley graph, where
H =hr,l |r^{s} =l^{2} = (rl)^{3} = 1, . . .i is a finite quotient

of the modular group PSL(2,Z). ThenK has a Hamilton path.

Moreover, if |H| ≡2 (mod 4)or if |r| ≡0,±1 (mod 4), then K has a Hamilton cycle.

Question 1.

What about the missing case |H| ≡0 (mod 4)and|r| ≡2 (mod 4)? Question 2.

What about the finite quotients of the group

hx,y,z |x^{2}=y^{2}=z^{2} = (xy)^{3}= (yz)^{3}= 1, . . .i ?

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 3 / 32

## Hamilton cycles in cubic Cayley graphs

Theorem (Glover, Maruˇsiˇc, Kutnar, Malniˇc, 2007–2012)
Let K =Cay(H;r,r^{−1},l) be a cubic Cayley graph, where
H =hr,l |r^{s} =l^{2} = (rl)^{3} = 1, . . .i is a finite quotient

of the modular group PSL(2,Z). ThenK has a Hamilton path.

Moreover, if |H| ≡2 (mod 4)or if |r| ≡0,±1 (mod 4), then K has a Hamilton cycle.

Question 1.

What about the missing case |H| ≡0 (mod 4)and|r| ≡2 (mod 4)?

Question 2.

What about the finite quotients of the group

hx,y,z |x^{2}=y^{2}=z^{2} = (xy)^{3}= (yz)^{3}= 1, . . .i ?

## Hamilton cycles in cubic Cayley graphs

Theorem (Glover, Maruˇsiˇc, Kutnar, Malniˇc, 2007–2012)
Let K =Cay(H;r,r^{−1},l) be a cubic Cayley graph, where
H =hr,l |r^{s} =l^{2} = (rl)^{3} = 1, . . .i is a finite quotient

of the modular group PSL(2,Z). ThenK has a Hamilton path.

Moreover, if |H| ≡2 (mod 4)or if |r| ≡0,±1 (mod 4), then K has a Hamilton cycle.

Question 1.

What about the missing case |H| ≡0 (mod 4)and|r| ≡2 (mod 4)?

Question 2.

What about the finite quotients of the group

hx,y,z |x^{2}=y^{2}=z^{2} = (xy)^{3}= (yz)^{3} = 1, . . .i?

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 3 / 32

## Proof: topological background

*l*
*r*

## Proof: topological background

Main idea

Take the Cayley mapM corresponding to
H =hr,l |r^{s} =l^{2} = (rl)^{3}= 1, . . .i

Select a suitable setF of faces ofMsuch thatSF isconnectedand null-homologous, i.e., a ‘tree’of faces.

Construct a Hamilton cycle as the topological boundary∂(SF)
The result is acontractible Hamilton cycle in CM(H;r,r^{−1},l).

The idea of constructing a Hamilton cycle as a boundary of a set of faces of map goes back to W. R. Hamilton (1858).

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 5 / 32

Do we need symmetry?

Do we need orientability?

Do we need contractibleHamilton cycles?

## Bounding Hamilton cycles in embedded graphs

Definition 1. LetK ,→S be a graph embedded in a closed surface S and let B ⊆K. We say that B is one-sidedin S ifS−B is connected and the boundary is also connected.

Example: Atree in an embedded graph is always one-sided.

Definition 2. LetG ,→S be an embedding of a graph forming polytopal map M. Aweak 2-face colouringof Mis a colouring of faces ofMwith two colours s.t. at each vertex of there are precisely two edges separating differently coloured faces.

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 7 / 32

## Bounding Hamilton cycles in embedded graphs

Definition 1. LetK ,→S be a graph embedded in a closed surface S and let B ⊆K. We say that B isone-sided inS ifS−B is connected and the boundary is also connected.

Example: Atree in an embedded graph is always one-sided.

Definition 2. LetG ,→S be an embedding of a graph forming polytopal map M. Aweak 2-face colouringof Mis a colouring of faces ofMwith two colours s.t. at each vertex of there are precisely two edges separating differently coloured faces.

## Bounding Hamilton cycles in embedded graphs

Definition 1. LetK ,→S be a graph embedded in a closed surface S and let B ⊆K. We say that B isone-sided inS ifS−B is connected and the boundary is also connected.

Example: Atree in an embedded graph is always one-sided.

Definition 2. LetG ,→S be an embedding of a graph forming polytopal map M. Aweak 2-face colouringof Mis a colouring of faces ofMwith two colours s.t. at each vertex of there are precisely two edges separating differently coloured faces.

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 7 / 32

## Bounding Hamilton cycles in embedded graphs

Definition 1. LetK ,→S be a graph embedded in a closed surface S and let B ⊆K. We say that B isone-sided inS ifS−B is connected and the boundary is also connected.

Example: Atree in an embedded graph is always one-sided.

## Bounding Hamilton cycles: characterisation

Theorem 1

Let Mbe a polytopal map on a closed surface of Euler genus g. The following statements are equivalent.

(i) Mhas a bounding Hamilton cycle.

(ii) The vertices of M^{∗} can be a partitioned into two subsets which
induceone-sided subgraphs H and K such that β(H) +β(K) =g.
(iii) Mhas a weak2-face-colouring such that the vertices of M^{∗}

receiving colour 1 induce a one-sided subgraph ofM^{∗}.

Theorem 2

A polytopal map Madmits acontractible Hamilton cycle ⇐⇒
M has aweak2-face-colouring such that the vertices of M^{∗} receiving
colour1 induce a tree.

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 8 / 32

## Bounding Hamilton cycles: characterisation

Theorem 1

Let Mbe a polytopal map on a closed surface of Euler genus g. The following statements are equivalent.

(i) Mhas a bounding Hamilton cycle.

(ii) The vertices of M^{∗} can be a partitioned into two subsets which
induceone-sided subgraphs H and K such that β(H) +β(K) =g.
(iii) Mhas a weak2-face-colouring such that the vertices of M^{∗}

receiving colour 1 induce a one-sided subgraph ofM^{∗}.

Theorem 2

A polytopal map Madmits acontractible Hamilton cycle ⇐⇒

Mhas a weak2-face-colouring such that the vertices of M^{∗} receiving
colour1 induce a tree.

## Remarks

Remark 1

According to the Strong Embedding Conjecture, every 2-connected graph has a polytopal embedding.

=⇒ Theorem 1 can potentially be applied toall2-connected graphs.

Remark 2

Part (ii) of Theorem 1 implies that a Hamilton cycle in a planar map M
corresponds to a vertex partition of M^{∗} into two induced trees.

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 9 / 32

## Remarks

Remark 1

According to the Strong Embedding Conjecture, every 2-connected graph has a polytopal embedding.

=⇒ Theorem 1 can potentially be applied toall2-connected graphs.

Remark 2

Part (ii) of Theorem 1 implies that a Hamilton cycle in a planar map M
corresponds to a vertex partition of M^{∗} into two induced trees.

## Hamilton cycles in 2-face-coloured cubic polytopal maps

In certain cases a map may be given an initial2-face-colouring.

Typical example: truncated maps t(M) vertex-faces 7→ colour0

face-faces 7→ colour1

Theorem

Let Mbe a cubic polytopal map with a fixed weak2-face colouring. If the
vertices of M^{∗} receiving colour 1can be partitioned into an induced tree
and anindependent set, then Madmits acontractibleHamilton cycle.

Theorem

A connected cubic graph G admits a partition of its vertex-set into an induced treeand anindependent set ⇐⇒

G has cellular embedding into an orientable surface with a single face.

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 10 / 32

## Hamilton cycles in 2-face-coloured cubic polytopal maps

In certain cases a map may be given an initial2-face-colouring.

Typical example: truncated maps t(M) vertex-faces 7→ colour0

face-faces 7→ colour1

Theorem

Let Mbe a cubic polytopal map with a fixed weak2-face colouring. If the
vertices of M^{∗} receiving colour 1can be partitioned into an induced tree
and anindependent set, then Madmits acontractibleHamilton cycle.

Theorem

A connected cubic graph G admits a partition of its vertex-set into an induced treeand anindependent set ⇐⇒

G has cellular embedding into an orientable surface with a single face.

## Hamilton cycles in 2-face-coloured cubic polytopal maps

In certain cases a map may be given an initial2-face-colouring.

Typical example: truncated maps t(M) vertex-faces 7→ colour0

face-faces 7→ colour1

Theorem

Let Mbe a cubic polytopal map with a fixed weak2-face colouring. If the
vertices ofM^{∗} receiving colour 1can be partitioned into an induced tree
and anindependent set, then Madmits acontractibleHamilton cycle.

Theorem

A connected cubic graph G admits a partition of its vertex-set into an induced treeand anindependent set ⇐⇒

G has cellular embedding into an orientable surface with a single face.

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 10 / 32

## Hamilton cycles in 2-face-coloured cubic polytopal maps

In certain cases a map may be given an initial2-face-colouring.

Typical example: truncated maps t(M) vertex-faces 7→ colour0

face-faces 7→ colour1

Theorem

Let Mbe a cubic polytopal map with a fixed weak2-face colouring. If the
vertices ofM^{∗} receiving colour 1can be partitioned into an induced tree
and anindependent set, then Madmits acontractibleHamilton cycle.

Theorem

G has cellular embedding into an orientable surface with a single face.

## Contractible Hamilton cycles in truncated triangulations

Every truncated triangulation t(T) has a natural weak 2-face-colouring vertex-faces 7→ colour0

face-faces 7→ colour1

Theorem

Let T be a triangulation of a closed surface and let t(T) be the truncation of T. The following statements are equivalent.

(i) t(T)has a contractible Hamilton cycle.

(ii) The vertex set of T^{∗} admits a partition{A,J}whereAinduces a tree
in the underlying graph ofT^{∗} andJ isindependent.

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 11 / 32

END OF PART I

Thank you!

HAMILTON CYCLES IN EMBEDDED GRAPHS

PART II

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 13 / 32

## Truncated triangulations

*l*
*r*

## Contractible Hamilton cycles in truncated triangulations

Every truncated triangulation t(T) has a natural weak 2-face-colouring vertex-faces 7→ colour0

face-faces 7→ colour1

Observation

The subgraph of t(T)^{∗} induced by the vertices of colour 1is isomorphic to
the underlying graph of T^{∗} and is therefore cubic.

Theorem

Let T be a triangulation of a closed surface and let t(T) be the truncation of T. The following statements are equivalent.

(i) t(T)has a contractible Hamilton cycle.

(ii) The vertex set of T^{∗} admits a partition{A,J}whereAinduces a tree
in the underlying graph ofT^{∗} andJ isindependent.

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 15 / 32

## Contractible Hamilton cycles in truncated triangulations

Every truncated triangulation t(T) has a natural weak 2-face-colouring vertex-faces 7→ colour0

face-faces 7→ colour1 Observation

The subgraph of t(T)^{∗} induced by the vertices of colour 1is isomorphic to
the underlying graph of T^{∗} and is therefore cubic.

Theorem

Let T be a triangulation of a closed surface and let t(T) be the truncation of T. The following statements are equivalent.

(i) t(T)has a contractible Hamilton cycle.

(ii) The vertex set of T^{∗} admits a partition{A,J}whereAinduces a tree
in the underlying graph ofT^{∗} andJ isindependent.

## Contractible Hamilton cycles in truncated triangulations

Every truncated triangulation t(T) has a natural weak 2-face-colouring vertex-faces 7→ colour0

face-faces 7→ colour1 Observation

The subgraph of t(T)^{∗} induced by the vertices of colour 1is isomorphic to
the underlying graph of T^{∗} and is therefore cubic.

Theorem

(i) t(T)has a contractible Hamilton cycle.

^{∗} admits a partition{A,J}whereAinduces a tree
in the underlying graph ofT^{∗} andJ isindependent.

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 15 / 32

## Example: Construction of a Hamilton cycle in t(T )

## Example: Construction of a Hamilton cycle in t(T )

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 17 / 32

## Example: Construction of a Hamilton cycle in t(T )

## Example: Construction of a Hamilton cycle in t(T )

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 19 / 32

## Example: Construction of a Hamilton cycle in t(T )

## Example: Construction of a Hamilton cycle in t(T )

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 21 / 32

## Example: The required Hamilton cycle

## When does such a structure exist?

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 23 / 32

## Vertex-partitions in cubic graphs

Theorem

The following are equivalent for every connected cubic graph G . (i) V(G) has a partition{A,J}where Ainduces a tree andJ is

independent.

(ii) G has an orientable cellular embedding with a single face.

## Contractible Hamilton cycles in truncated triangulations

Theorem

(i) t(T)has a contractible Hamilton cycle.

(ii) The underlying graph of T^{∗} admits an orientable cellular embedding
with asingle face.

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 25 / 32

## Corollaries

Corollary

Let T be a triangulation of a closed surface with f faces. If T has no separating 3-cycles, then its trucation admits a Hamilton path. Moreover, t(T) has acontractible Hamilton cycle in each of the following cases:

(i) f ≡2 (mod 4)

(ii) T^{∗} is cyclically 5-connected andT has a vertex of degree0 (mod 4).

(iii) T^{∗} is cyclically 6-connected andT has two adjacent vertices with
degrees deg(u)≡deg(v)≡ ±1 (mod 4).

## Interesting example

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 27 / 32

## A unified approach to results of Glover, Maruˇsiˇ c et al.

Theorem

Let K =Cay(H;r,r^{−1},l) be a cubic Cayley graph, where
H =hr,l |r^{s} =l^{2} = (rl)^{3} = 1, . . .i is a finite quotient
of the modular group PSL(2,Z). Then the following hold.

(i) K has a Hamilton path.

(ii) K has abounding Hamilton cycle with respect to its natural embedding as a Cayley map CM(H;r,l) ⇐⇒

|H| ≡2 (mod 4)or if|r| ≡0,±1 (mod 4).

Furthemore, if CM(H;r,l)has a bounding Hamilton cycle, then it has a contractible one.

## A unified approach to results of Glover, Maruˇsiˇ c et al.

Proof of (ii).

“=⇒”: Construction.

“⇐=”: Counting argument: Theorem

Let Mbe a polytopal map withn vertices and let Q be a one-sided
subgraph of M^{∗} determining a bounding Hamilton cycle in M.
Ifβ(Q) =b, then

X

v∈V(Q)

(deg(v)−2)−2b+ 2 =n.

In our case, M=CM(H;r,l) is orientable, so Q must have an even Betti number. Hence n =|H|=2 (mod 4), a contradiction.

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 29 / 32

## A unified approach to results of Glover, Maruˇsiˇ c et al.

Proof of (ii).

“=⇒”: Construction.

“⇐=”: Counting argument:

Theorem

Let Mbe a polytopal map withn vertices and let Q be a one-sided
subgraph of M^{∗} determining a bounding Hamilton cycle in M.
Ifβ(Q) =b, then

X

v∈V(Q)

(deg(v)−2)−2b+ 2 =n.

In our case, M=CM(H;r,l) is orientable, so Q must have an even Betti number. Hence n =|H|=2 (mod 4), a contradiction.

## A unified approach to results of Glover, Maruˇsiˇ c et al.

Proof of (ii).

“=⇒”: Construction.

“⇐=”: Counting argument:

Theorem

Let Mbe a polytopal map withn vertices and let Q be a one-sided
subgraph of M^{∗} determining a bounding Hamilton cycle in M.

Ifβ(Q) =b, then

X

v∈V(Q)

(deg(v)−2)−2b+ 2 =n.

In our case, M=CM(H;r,l) is orientable, so Q must have an even Betti number. Hence n =|H|=2 (mod 4), a contradiction.

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 29 / 32

## A unified approach to results of Glover, Maruˇsiˇ c et al.

Proof of (ii).

“=⇒”: Construction.

“⇐=”: Counting argument:

Theorem

Let Mbe a polytopal map withn vertices and let Q be a one-sided
subgraph of M^{∗} determining a bounding Hamilton cycle in M.

Ifβ(Q) =b, then

X

v∈V(Q)

(deg(v)−2)−2b+ 2 =n.

In our case, M=CM(H;r,l) is orientable, so Q must have an even Betti number. Hence n=|H|=2 (mod 4), a contradiction.

## Truncations of Coxeter triangulations of the torus

Coxeter and Moser classified regular toroidal triangulations as{3,6}_{b,c}
where b andc are non-negative integer parameters. The size of the
orientation-preserving automorphism group is 6(b^{2}+bc +c^{2}).

Corollary

The truncation of {3,6}_{b,c} has abounding Hamilton cycle ⇐⇒
at least one of b andc is odd.

Altshuler (1972)proved that all these graphs are hamiltonian.

=⇒ Ifb andc are even, then all Hamilton cycles arenon-bounding.

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 30 / 32

## Truncations of Coxeter triangulations of the torus

Coxeter and Moser classified regular toroidal triangulations as{3,6}_{b,c}
where b andc are non-negative integer parameters. The size of the
orientation-preserving automorphism group is 6(b^{2}+bc +c^{2}).

Corollary

The truncation of {3,6}_{b,c} has abounding Hamilton cycle ⇐⇒

at least one of b andc is odd.

Altshuler (1972)proved that all these graphs are hamiltonian.

=⇒ Ifb andc are even, then all Hamilton cycles arenon-bounding.

## Truncations of Coxeter triangulations of the torus

Coxeter and Moser classified regular toroidal triangulations as{3,6}_{b,c}
where b andc are non-negative integer parameters. The size of the
orientation-preserving automorphism group is 6(b^{2}+bc +c^{2}).

Corollary

The truncation of {3,6}_{b,c} has abounding Hamilton cycle ⇐⇒

at least one of b andc is odd.

Altshuler (1972)proved that all these graphs are hamiltonian.

=⇒ Ifb andc are even, then all Hamilton cycles arenon-bounding.

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 30 / 32

## Hamiltonicity of three-involution cubic Cayley graphs

Theorem

Let K =Cay(H;x,y,z) be a cubic Cayley graph, where
H =hx,y,z |x^{2}=y^{2}=z^{2} = 1,(xy)^{3} = (yz)^{3} = 1, . . .i.

Then K admits abounding Hamilton cycle with respect to the natural associated embedding ⇐⇒ |H| ≡2 (mod 4)or |xz|is even.

Furthemore, if K has a bounding Hamilton cycle (with respect to the natural embedding), then it has a contractible one.

Thank you!

Roman Nedela and Martin ˇSkoviera Hamilton cycles 15/02/2016 32 / 32