Hamiltonian Cycles in Subdivided Doubles

David Eppstein · 2025

Read Hamiltonian Cycles in Subdivided Doubles by David Eppstein (2025) 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-2510-18359.txt.

Introduction

David Eppstein, writing alone, studies a construction in graph theory called the subdivided double. A graph is a network of points joined by lines, and here each graph under study has four lines at every point. Earlier researchers used subdivided doubles to build and study semi-symmetric graphs, which look the same along their edges but not at their points.

Eppstein proves that these graphs have a further property that does not depend on symmetry at all. Each one contains a very large number of Hamiltonian cycles, meaning closed routes that visit every point exactly once before returning to the start. Better still, every such cycle can be paired with a second cycle that complements it, so the two routes together cover the graph in a balanced way.

Catalog record

CREATORDavid Eppstein
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE19 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-18359

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Hamiltonian Cycles in Subdivided Doubles David Eppstein Abstract The subdivided double construction on 4-regular graphs was used by Potočnik and Wilson to explore semi-symmetric (edge-transitive but not vertex-transitive) graphs, and can be used to construct every semi-symmetric 4-regular graph that contains a pair of twin vertices. We show that (regardless of symmetry) subdivided doubles have another curious property: they have exponentially many Hamiltonian cycles each of which is complementary to another Hamiltonian cycle. 1 Introduction In a 4-regular graph, the complement of a Hamiltonian cycle is another 2-regular spanning subgraph, which might or might not be another Hamiltonian cycle. In K_{5} , for instance, the only 2-regular spanning subgraphs are 5-cycles, so each Hamiltonian cycle is complementary to another one. In the octahedral graph K_{2,2,2} , however, some Hamiltonian cycles are complementary to pairs of disjoint triangles. Because there is no reason to expect any special structure such as connectedness in the complements of Hamiltonian cycles, we expect the behavior of K_{2,2,2} to be the more typical case for large Hamiltonian 4-regular graphs. Potočnik and Wilson used subdivided doubles , a method for transforming 4-regular graphs into larger 4-regular graphs, to analyze the structure of semi-symmetric graphs (the regular and edge-transitive but not vertex-transitive graphs) [ 9 , 10 ] . This construction produces graphs having many Hamiltonian cycles (some of them coming from Euler tours of the underlying graph). In this paper we prove that all subdivided doubles share with K_{5} the property that every Hamiltonian cycle is complementary to another Hamiltonian cycle. For our convenience, we give this property a name: Definition 1 . A 4-regular graph is Hamiltonian-paired if it is Hamiltonian and the complement of every Hamiltonian cycle is another Hamiltonian cycle. With this definition established, we can express our main result succinctly: every subdivided double is Hamiltonian-paired. When a 4-regular graph has two complementary Hamiltonian cycles, they form a Hamiltonian decomposition . Every 4-regular graph has an even number of Hamiltonian decompositions [ 11 ] . A line graph of a cubic graph has a Hamiltonian decomposition if and only if the underlying cubic graph has a Hamiltonian cycle [ 6 , 7 ] . Because testing Hamiltonicity of cubic planar graphs is \mathsf{NP} -complete [ 3 ] , it is also \mathsf{NP} -complete to test the existence of a Hamiltonian decomposition in the line graph of a cubic planar graph, and more generally in any 4-regular planar graph. These remarks also resolve a 2012 conjecture of Cygan et al. [ 1 ] on the complexity of linear arboricity. A linear forest is a union of vertex-disjoint paths, and the linear arboricity of a graph is the minimum number of linear forests into which the edges of the graph can be partitioned. If a 4-regular graph has a Hamiltonian decomposition, then removing an arbitrary vertex turns its two Hamiltonian cycles into two Hamiltonian paths, showing that the graph with the removed vertex has linear arboricity two. On the other hand, if a 4-regular graph does not have a Hamiltonian decomposition, then removing a single vertex cannot produce a graph with linear arboricity two, because two linear forests that are not both Hamiltonian paths do not have enough edges to cover all edges of the resulting graph, and a cover by two Hamiltonian paths would necessarily terminate the paths at the four odd-degree vertices left as the neighbors of the removed vertex, giving a Hamiltonian decomposition. Because it is \mathsf{NP} -complete to test the existence of a Hamiltonian decomposition in a 4-regular planar graph, it is \mathsf{NP} -complete to test whether the subgraph obtained by removing any single vertex has linear arboricity two. Therefore, more generally, it is \mathsf{NP} -complete to test whether a planar graph has linear arboricity two, as was conjectured by Cygan et al. Almost all 4-regular graphs, and almost all 4-regular bipartite graphs, have Hamiltonian decompositions [ 2 , 5 , 4 ] Our results show that, despite the hardness of finding Hamiltonian decompositions in arbitrary 4-regular graphs, they are easy to find in subdivided doubles. Figure 1: The two steps of the subdivided double construction, applied to the octahedral graph K_{2,2,2} (left): subdivide each edge (center), and then double each degree-four vertex of the result to produce the subdivided double \operatorname{SDD}(K_{2,2,2}) (right). 2 Subdivided doubles We begin by reviewing the definition of a subdivided double from Potočnik and Wilson [ 9 , 10 ] . Following the notation of Potočnik, Verret, and Wilson [ 8 ] , we denote by \operatorname{SDD}(G) the subdivided double of any 4-regular graph G . Definition 2 . \operatorname{SDD}(G) is constructed as follows. First, subdivide each edge of G into a two-edge path, producing a bipartite biregular graph with degree-four vertices on one side of the bipartition (the original vertices of G ) and degree-two vertices on the other side (the subdivision vertices). Then, replace each degree-four vertex by a pair of twin vertices, not adjacent to each other but sharing the same four neighbors. The resulting graph is 4-regular, as the replacement of each degree-four vertex by twins doubles the degree of the subdivision vertices from two to four, while not changing the degree of the replaced twin vertices. Fig. 1 shows the application of this process to the octahedral graph K_{2,2,2} , producing its subdivided double \operatorname{SDD}(K_{2,2,2}) . Figure 2: The circulant graph C_{16}^{1,7} formed as the subdivided double of a 4-cycle with doubled edges (left) is Hamiltonian-paired; the outer polygon and inner star polygon form a Hamiltonian decomposition. The circulant graph C_{18}^{1,8} (right) is not Hamiltonian-paired, despite having the same local structure; the outer polygon is a Hamiltonian cycle but its complement is a pair of cycles (red and blue) rather than a single Hamiltonian cycle. As Potočnik and Wilson observe, the subdivided double of any arc-transitive simple graph is edge-transitive, and every 4-regular semi-symmetric graph with a pair of twin vertices arises in this way. In particular, the Folkman graph ( Figs. 3 and 4 ), the smallest semi-symmetric graph, is the subdivided double \operatorname{SDD}(K_{5}) of K_{5} [ 9 , 10 ] . It is also possible to apply the subdivided double construction to 4-regular multigraphs as well as to simple graphs. In particular: • If D_{n} denotes the two-vertex dipole multigraph with n edges connecting its two vertices, then \operatorname{SDD}(D_{4})=K_{4,4} . • If \bar{\bar{C}}_{n} denotes the multigraph formed by doubling each edge in an n -vertex cycle, then \operatorname{SDD}(\bar{\bar{C}}_{n}) is a circulant graph C_{4n}^{1,2n-1} , formed from a cyclic sequence of 4n vertices by connecting pairs of vertices that are one or 2n-1 step apart in the sequence. The twin of each vertex is the vertex opposite it in the cyclic sequence. Fig. 2 depicts the circulant C_{16}^{1,7} arising from the case n=4 . (These graphs can also be constructed as the lexicographic product C_{2n}\cdot 2K_{1} of a 2n -vertex cycle graph and a two-vertex edgeless graph.) Our results on subdivided doubles apply to the subdivided doubles of multigraphs, and not only to the subdivided doubles of simple graphs. It is easy to recognize the subdivided doubles algorithmically. They are the 4-regular bipartite graphs in which the vertices of one side of the bipartition can be paired up into twins. When

Read the complete text