Hamiltonicity of Transitive Graphs Whose Automorphism Group Has ℤ p \mathbb{Z}_{p} as Commutator Subgroups
Florian Lehner Farzad Maghsoudi Babak Miraftab · 2024
Read Hamiltonicity of Transitive Graphs Whose Automorphism Group Has ℤ p \mathbb{Z}_{p} as Commutator Subgroups by Florian Lehner Farzad Maghsoudi Babak Miraftab (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-08105.txt.
Introduction
A Hamiltonian cycle visits every vertex of a graph exactly once before returning to the start, and finding one is a classic test of a graph's structure. Florian Lehner, Farzad Maghsoudi, and Babak Miraftab extend a 1982 result in 2024 from finite to infinite graphs. The old theorem covered Cayley graphs of groups whose commutator subgroup has prime order.
The new version reaches a wider family of endless graphs: any connected graph whose symmetry group includes a subgroup that acts transitively and whose commutator is a cyclic group of prime order. Such graphs, they prove, always contain a Hamiltonian cycle. The result carries a finite-group guarantee into the infinite world, where cycles must be built without end.
Catalog record
| CREATOR | Florian Lehner Farzad Maghsoudi Babak Miraftab |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 45 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-08105
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hamiltonicity of Transitive Graphs Whose Automorphism Group Has ℤ p \mathbb{Z}_{p} as Commutator Subgroups Florian Lehner Farzad Maghsoudi Babak Miraftab Abstract In 1982, Durnberger proved that every connected Cayley graph of a finite group with a commutator subgroup of prime order contains a hamiltonian cycle. In this paper, we extend this result to the infinite case. Additionally, we generalize this result to a broader class of infinite graphs X X , where the automorphism group of X X contains a transitive subgroup G G with a cyclic commutator subgroup of prime order. \DeclareMathOperator \interior Int \DeclareMathOperator \VE VE 1 Introduction A hamiltonian path (cycle) in a finite graph is a path (cycle) that traverses every vertex of the graph exactly once. A graph X is called vertex-transitive if its automorphism group acts transitively on its vertices, in other words, for any two vertices v_{1} and v_{2} in V(X) , there exists an automorphism f\colon V(X)\to V(X) such that f(v_{1})=v_{2} . Lovász in 1969 conjectured that every finite connected vertex transitive graph has a hamiltonian path [ 10 , p 497] , but even decades later this conjecture remains largely unresolved. A particularly significant class of transitive graphs is the class of Cayley graphs. Lovász’ conjecture has been verified for certain classes of Cayley graphs, such as Abelian groups, p -groups [ 20 ] , and groups whose order has few prime factors [ 11 ] , see the surveys [ 21 , 12 ] for more results. Hamiltonicity problems have also received significant attention in the context of infinite graphs, as evidenced by recent studies [ 15 , 16 , 14 , 7 , 1 ] . It is worth noting that there are several appropriate generalizations of hamiltonian cycles for infinite graphs. In this paper, our focus is on two-way hamiltonian paths. Definition 1 (cf. [ 18 , pp. 286 and 297] ) . Let X be a countably infinite graph. A two-way hamiltonian path is a two-way infinite list \ldots,x_{-2},x_{-1},x_{0},x_{1},x_{2},\ldots containing each vertex of X exactly once, such that x_{i} is adjacent to x_{i+1} for each i . Many results about hamiltonian paths in finite graphs carry over to the infinite setting. For instance, the following result is well-known. Lemma 1 . Let G be a finitely generated abelian group. Then the following holds: 1. [ 13 , Corollary 3.2] If G is finite, then every Cayley graph of G has a hamiltonian cycle. 2. [ 17 , Theorem 1] If G is infinite, then every Cayley graph of G has a two-way hamiltonian path. Recall that the commutator subgroup G^{\prime} of a group G is the subgroup generated by all commutators \langle[x,y]=xyx^{-1}y^{-1}\mid x,y\in G\rangle , so G is abelian if and only if the commutator subgroup of G is trivial. Since Lovász’ conjecture is known to be true for Cayley graphs of abelian groups, it seems natural to explore scenarios where the order of the commutator subgroup of G is small. In 1982, Durnberger proved the following: Theorem 2 . [ 6 , Theorem 1] There is a hamiltonian cycle in every connected Cayley graph of a finite group whose commutator subgroup has prime order. Our first result is an extension of 2 to infinite locally finite Cayley graphs. Theorem 3 . Let G=\langle S\rangle with G^{\prime}\cong\mathbb{Z}_{p} . Then \mathop{\mathsf{Cay}}(G;S) has a two-way hamiltonian path. Then our next result is a generalization of the preceding theorem to infinite locally finite transitive graphs. Theorem 4 . Let X be an infinite locally finite G -transitive graph such that G^{\prime}\cong\mathbb{Z}_{p} . Then X has a two-way hamiltonian path. An overview of the proof techniques: We first prove that every Cayley graph of a finitely generated group G , where G^{\prime}\cong\mathbb{Z}_{p} , contains a two-way hamiltonian path. We then extend this result to infinite, locally finite, transitive graphs whose automorphism groups have a commutator subgroup that is cyclic of prime order. The first step in the proof of Theorem 3 is to find a two-way hamiltonian path \gamma in a Cayley graph of G/G^{\prime} together with an infinite set of edges F aligned with \gamma , see Figure 1 for a sketch. More precisely, we define the following: Definition 2 . Let X be a multigraph and let \gamma\colon\ldots,v_{-1},v_{0},v_{1},\ldots be a two-way-infinite path in X . Call an infinite sequence \{e_{\ell}=(x_{\ell},y_{\ell})\mid\ell\in\mathbb{Z}\} of edges of X aligned with \gamma if none of the edges e_{\ell} is contained in \gamma , and for every \ell\in\mathbb{Z} there is some j\in\mathbb{Z} and k\geq 1 such that x_{\ell}=v_{j} , y_{\ell}=v_{j+k} , and x_{\ell+1}=v_{j+k+1} . In this case, each edge e_{\ell} is called jumping , see Figure 1 . We note that the case k=1 in the above definition can only occur in multigraphs, since in this case the edge e_{\ell} is parallel to an edge in the infinite path \gamma . Figure 1: An example of a two-way infinite path aligned with [e_{\ell}\mid\ell\in\mathbb{Z}] . Notation 5 . If \gamma is a two-way infinite path aligned with a sequence [e_{\ell}=(x_{\ell},y_{\ell})\mid\ell\in\mathbb{Z}] , then adding an edge e_{\ell} to \gamma gives rise to a unique cycle. We denote this cycle by C_{\ell} . The second step in our strategy is to use an aligned sequence of edges to “lift” a hamiltonian path in a Cayley graph of G/G^{\prime} to a hamiltonian path in a Cayley graph of G . To simplify notation, we introduce the following notation, where usually N will be equal to G^{\prime} . Notation 6 . Let G be a group with a normal subgroup N . Then there is a projection homomorphism \pi\colon G\to G/N . For every subgroup(subset) of H of G , we denote the image of H under \pi by \overline{H} ; for every g\in G we denote the coset gN by \overline{g} . Let’s return to the strategy. Since we assume that G^{\prime} is finite, each cycle C_{\ell} in the Cayley graph G/G^{\prime} lifts to a finite subgraph of the Cayley graph of G , referred to as a block ( \pi^{-1}(C_{\ell}) ), see Figure 2 . The trickiest part of the proof is finding a hamiltonian path with an aligned sequence that ensures that each block has a hamiltonian cycle. To this end, we use the concept of voltage. Definition 3 (cf. [ 8 ] ) . Let G=\langle S\rangle be a group, where S is finite, and let N be a normal subgroup of G . Let C\coloneqq\overline{g}(\overline{s_{1}},\ldots,\overline{s_{n}}) be a cycle in \mathop{\mathsf{Cay}}(\overline{G};\overline{S}) . The voltage of C denoted by \mathsf{Volt}(C) is defined as the product s_{1}\cdots s_{n} . It can be shown (see 13 ) that if the voltage of C_{\ell} is non-trivial, then the corresponding block has a hamiltonian cycle. Finally, if every block has a hamiltonian cycle, we can combine suitable hamiltonian paths within each block to form a two-way hamiltonian path in the Cayley graph of G , see Figure 3 . Next, let X be a locally finite graph, where a group G acts transitively on X and G^{\prime}=\mathbb{Z}_{p} . We leverage the existence of a two-way hamiltonian path in a Cayley graph to construct a two-way hamiltonian path in X . More specifically, we consider the quotient graph X/G^{\prime} , which is