HAMILTON CYCLES IN EMBEDDED GRAPHS

(1)

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

(2)

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

(3)

Lov´ asz problem

(4)

Lov´ asz problem

(5)

Hamilton cycles in cubic Cayley graphs

Theorem (Glover, Maruˇsiˇc, Kutnar, Malniˇc, 2007–2012) Let K =Cay(H;r,r⁻¹,l) be a cubic Cayley graph, where H =hr,l |r^s =l² = (rl)³ = 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²=y²=z² = (xy)³= (yz)³= 1, . . .i ?

(6)

Hamilton cycles in cubic Cayley graphs

Question 1.

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

Question 2.

hx,y,z |x²=y²=z² = (xy)³= (yz)³= 1, . . .i ?

(7)

Hamilton cycles in cubic Cayley graphs

Question 1.

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

Question 2.

hx,y,z |x²=y²=z² = (xy)³= (yz)³ = 1, . . .i?

(8)

Proof: topological background

l r

(9)

Proof: topological background

Main idea

Take the Cayley mapM corresponding to H =hr,l |r^s =l² = (rl)³= 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⁻¹,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).

(10)

Do we need symmetry?

Do we need orientability?

Do we need contractibleHamilton cycles?

(11)

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.

(12)

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.

(13)

Bounding Hamilton cycles in embedded graphs

(14)

Bounding Hamilton cycles in embedded graphs

(15)

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.

(16)

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.

(17)

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.

(18)

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.

(19)

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.

(20)

Hamilton cycles in 2-face-coloured cubic polytopal maps

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

(21)

Hamilton cycles in 2-face-coloured cubic polytopal maps

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

(22)

Hamilton cycles in 2-face-coloured cubic polytopal maps

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

(23)

Contractible Hamilton cycles in truncated triangulations

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

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.

(24)

END OF PART I

Thank you!

(25)

HAMILTON CYCLES IN EMBEDDED GRAPHS

PART II

(26)

Truncated triangulations

l r

(27)

Contractible Hamilton cycles in truncated triangulations

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

(28)

Contractible Hamilton cycles in truncated triangulations

face-faces 7→ colour1 Observation

Theorem

(29)

Contractible Hamilton cycles in truncated triangulations

face-faces 7→ colour1 Observation

Theorem

(30)

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

(31)

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

(32)

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

(33)

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

(34)

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

(35)

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

(36)

Example: The required Hamilton cycle

(37)

When does such a structure exist?

(38)

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.

(39)

Contractible Hamilton cycles in truncated triangulations

Theorem

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

(40)

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).

(41)

Interesting example

(42)

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

Theorem

Let K =Cay(H;r,r⁻¹,l) be a cubic Cayley graph, where H =hr,l |r^s =l² = (rl)³ = 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.

(43)

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.

(44)

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

Proof of (ii).

“⇐=”: 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.

(45)

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

Proof of (ii).

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.

(46)

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

Proof of (ii).

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.

(47)

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²+bc +c²).

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.

(48)