# On Hamiltonian Decomposition Problem of 3-Arc Graphs

Authors: Guangjun Xu; Qiang Sun; Zuosong Liang
Journal: Computational Intelligence and Neuroscience
 (2022)

---

## Abstract

A 4-tupley,x,v,w in a graph is a 3-arc if each of y,x,v and x,v,w is a path. The 3-arc graph of H is the graph with vertex set all arcs of H and edge set containing all edges joining xy and vw whenever y,x,v,w is a 3-arc of H. A Hamilton cycle is a closed path meeting each vertex of a graph. A graph H including a Hamilton cycle is called Hamiltonian and H has a Hamiltonian decomposition provided its edge set admits a partition into disjoint Hamilton cycles (possibly with a single perfect matching). The current paper proves that every connected 3-arc graph consists of more than one Hamilton cycle. Since the 3-arc graph of a cubic graph is 4-regular, it further proves that each 3-arc graph of a cubic graph in a certain family has a Hamiltonian decomposition.


---

## Body

## 1. Introduction

A path (cycle) in a graph passing each vertex is said to be aHamilton path (cycle). A graph is hamiltonian if it consists of a Hamilton cycle and is Hamilton-connected if every pair of vertices are joined by a Hamilton path. A partition of the edge set EG into Hamilton cycles (or plus a perfect matching when G is k-regular with k odd) is called a Hamiltonian decomposition of G. The Hamiltonian problems and related topics are classical in combinatorics and have been received extensive treatment. See [1–3] for more results on this area of investigation.The current paper concentrates on the class of 3-arc graphs. This class of graphs is produced from a graph operation named 3-arc graph operation, which is similar to a line graph operation. This operation was initially introduced in [4] in exploring certain families of imprimitive symmetric graphs. It was also exploited in investigating several classes of symmetric graphs. See [4, 5] and references therein.We consider only a graph with finite order and undirected without loops. The termmultigraph is used if there are multiple edges connecting the same pair of vertices. An arc of H=VH,EH is a directed edge. If x,y are adjoined in H, we write xy to denote the directed edge outgoing from x to y, yx≠xy the directed edge from y to x, and x,y the edge connecting x and y. A 4-tuple y,x,v,w in a graph is a 3-arc if each of y,x,v and x,v,w is isomorphic to a path on three vertices. It may happen that y=w. Suppose H is a multigraph. A walk in H of length t is as follows:(1)u0,e1,u1,…,ul−1,el,ul.With terms interchangely contained in vertex setVH and edge set EH, where uj−1 and uj are connected by an edge ej, 1≤j≤l. A walk is closed if its originating and ending vertices coincide and is a trail if its all edges are pairwise different. A trail passing all edges of H is an Eulerian trail, and an Eulerian tour is a closed Eulerian trail.We refer to [1] for terms and notation not mentioned. The degree of u in a graph H is written as du, and the minimum degree of H is denoted by δH. We use Av to denote the set of all arcs outgoing from v, and AG to represent the set of all arcs of G.In the following we give the formal definition of the 3-arc graph of a graphH.Definition 1.
LetH be a graph. The 3-arc graph XH of H, is the graph with vertex set AH and all edges connecting xy and vw whenever y,x,v,w is a 3-arc of H.We illustrate the definition of this construction by depicting the 3-arc graph of complete graphK4 on four vertices a,b,c and d (see Figure 1). For instance, both a,b,c,d and a,b,c,a are 3-arcs in K4. The first one defines the adjacent relation between arcs ba and cd, and the latter gives rise to the adjacency between ba and ca.Figure 1
The 3-arc graph ofK4.It is not hard to see thatXH is not directed with 2EH vertices and ∑x,y∈EHdx−1dy−1 edges. It is shown that XH can actually be obtained from LH of H by the next procedures: divide every vertex x,y of LH into two, i.e., xy and yx; for every pair of vertices a,b,x,y of LH that are at a distance 2 away in LH, say, a and x are adjoined in H, connect ab and xy. For more recent work in this direction, see [6]. Specifically, in [7], it is established that all connected graphs contain a Hamilton cycle.In 1975, Sheehan proposed the following famous conjecture:Conjecture 1 (Sheehan [8]).
Each Hamiltonian graph that is regular of degree 4 consists of no less than two Hamilton cycles.Motivated by Sheehan’s Conjecture and the work [7], we study the Hamiltonian decomposition problem for 3-arc graphs. We show every connected 3-arc graph contains a second Hamilton cycle, and the 3-arc graphs of a family of cubic graphs have Hamiltonian decompositions. As a corollary, we demonstrate that the 3-arc graph of a bipartite cubic graph includes one Hamiltonian decomposition.To confirm Sheehan’s conjecture for 3-arc graphs, we actually prove a stronger result which asserts that any connected 3-arc graph contains no less than two Hamilton cycles. As the 3-arc graph of a cubic graph is 4-regular. We show further that each 3-arc graph of a cubic graph in a certain family has a Hamiltonian decomposition.The primary results are presented as follows.Theorem 1.
LetG be with a maximum degree Δ and have a connected 3-arc graph XG. Then the number of Hamilton cycles of XG is no less than the following:(2)2,ifΔ=3or4;Δ−3Δ−3Δ−2Δ−4Δ,if≥5..Remark 1.
SinceΔ−3Δ−3/Δ−2Δ−4Δ=Δ−21/1+1/Δ−3Δ−3Δ, 1+1/Δ−3Δ−3 is increasing and(3)limΔ⟶∞1+1Δ−3Δ−3=e.Theorem 2.
SupposeG is a connected cubic graph. If G contains an even IS-C decomposition, then XG has a Hamiltonian decomposition.


## 2. Proof of Theorems1 and 2

We need the following notation and definitions.Acactus is a graph in which any two cycles have at most one vertex in common. In particular, a tree is a special cactus. A cycle is said to be an odd (resp., even) cycle if it consists of an odd (resp., even) number of edges.Definition 2.
LetA,B be a partition (i.e., VG:=A∪B and A∩B=∅) of VG. A,B is said to be an independent set-cactus (IS-C) decomposition of G if in G the set A induces an empty graph and B induces a (connected) cactus.Note that not every graph has an IS-C decomposition. For example, the complete graph on five or more vertices has no IS-C decomposition.Since trees are acyclic, as a convention, we define the length of each cycle (which does not exist) of a tree to be 0. A cactus is calledeven if the length of each cycle is even. We treat a tree as an even cactus. An IS-C decomposition is called even if every cycle in the cactus is even.Lemma 1.
Each connected cubic graph has an IS-C decomposition.Proof. SupposeG is a connected cubic graph. If every two cycles of G share one or less common vertex, then G itself is a cactus. Clearly, an IS-C decomposition, ∅,VG, say, exists.Suppose thatG has two distinct cycles sharing two or more common vertices. We construct an IS-C decomposition for G as follows: choose any two cycles C1,C2 that share at least two common vertices. Denote the maximal common path occurring on both C1 and C2 by P:x,…,x′P:x,…,x′; that is, any vertex not on P occurs on at most one of the two cycles C1 and C2. Then delete x from G and put it into the set A (A takes the role of the independent set). Note that each neighbour of x now has degree strictly less than 3, and hence occurs on at most one cycle in G−x. So, the resultant graph G−x is connected. To simplify notation, denote again by G the graph resulting after deleting x. If G still has two cycles C3,C4 that share at least two common vertices. Denote the maximal common path occurring on both C3 and C4 by y,…,y′. Note that y,y′∉Nx. Delete y and put it into A. Continue this process until the resultant graph becomes a cactus.Since, at each stage, the setA remains to be independent and the resulting graph stays to be connected, eventually A,VG−A becomes a desired IS-C decomposition.Though every cubic graph has an IS-C decomposition, not every cubic graph has an even IS-C decomposition. For instance,K4 has no even IS-C decomposition.A 2-trailu,x,v with the middle term x is said to be a visit tox. If u≠v, then u,x,v and v,x,u are viewed as different visits to x. When we u,x,vv,x,uare not concerned about the directions of and , or its orientation is unknown, we denote u,x,v. The following operation regarding two parallel edges will be needed.Definition 3.
Lete1,e2 be parallel edges joining two adjacent u,v of G∗, let ei be covered by a closed trail Ci of length at least 4, i=1,2. (It may happen that C1=C2). Then one of C1u∪C2u and C1v∪C2v, say C1v∪C2v, contains two visits with one covering e1 and the other covering e2. Denote these two visits by p1=u,e1,v,e3,v1 and p2=u,e2,v,e4,v2, where v1,v2 are two neighbors of v other than u, and, e3,e4 are edges between v and v1,v2 respectively. Split the two 2-trails p1,p2 at v and reconnect e1,e2 with e4,e3, respectively. We call this the edge-shift operation of C1,C2 with respect to e1,e2, and denote the resultant trail(s) by CC1,C2;e1,e2, or simply CC1;e1,e2 if C1=C2.Remark 2.
A few comments on Definition3 are ready:(1)
IfC1=C2, CC1;e1,e2 remains to be a single closed trail if and only if the orientations of e1 and e2 are reverse to each other in C1; in this case, this operation is, in fact, the edge version of the bow-tie operation (see, Definition 5 in [7]).(2)
IfC1=C2, CC1;e1,e2 is a set of two closed trails if and only if the orientations e1 and e2 are the same between u and v in C1.(3)
All edges covered byC1, C2 are covered by CC1,C2;e1,e2.(4)
After the edge-shift operation above, the three terms involved inp1,p2 are swapped. That is, p1 is transformed into u,v,v2, and p2 is transformed into u,v,v1. All other visits induced are kept or with orientation inverted.Proof of Theorem1.
SupposeG is a graph with XG connected. Clearly, ΔG≥3. Denote the set of degree-2 vertices of G by S2, the multigraph gained from G by doubling its every edge by G∗.
Suppose thatΔ=3. Since XG is connected, by [7], XG is Hamiltonian, and every vertex in G has degree 2 or 3, S2 is independent, and G−S2 is connected. Further, it can be observed that G−S2 contains at least 2 vertices. Suppose u,v are two adjacent vertices in G−S2, u′ is a neighbor of u different from v, and x,y are two distinct neighbors of v not equal u (it may occur that one of x,y equals u′). Denote P1:u′,u,v,x and P2:u′,u,v,y.
LetC1, C2 be two Eulerian tours of G∗ obtained without violating the condition (1) in Section 3 of [7], from extending P1,P2 to cover each edge of G∗, respectively. Apply the bow-tie operation (Definition 5 in [7]) when necessary to process Cj in such a way that the bipartite graph HCj′z (Definition 3 in [7]) with respect to the resultant Eulerian tour Cj′ has a perfect matching and the path Pj is a segment of Cj′, j=1,2. Note that both C1′ and C2′ exist. Consider C1. If HC1v has no perfect matching, then C1v contains twin visits by Lemma 1 in [7], that is, C1v=u,v,x,u,v,x,y,v,y. Apply the bow-tie operation to C1 with regard to y,v,y and anyone of the twin visits u,v,x that is not occurring on P1, we get a new Eulerian tour C1′=C1u,v,x,y,v,y, and one can observe that HC1′v is a perfect matching of 3 independent edges. The bow-tie operation can be performed similarly when necessary at u to produce a new Eulerian tour C1′ such that HC1′u has a perfect matching and the path Pj is maintained unchanged. It is analogous to showing that C2′ exists.
LetT1,T2 be two Hamilton cycles of XG derived from C1′, C2′, respectively. Denote the 3rd neighbor of u other than u′,v by w. Then one can observe that uw is connected to u′z,vy in T1, while connected to u′z′,vx in T2, where z,z′∈Nu′−u are not necessarily distinct. Since u′z,vy≠u′z′,vx, T1 and T2 are different Hamilton cycles of XG.
Suppose thatΔ≥4. Suppose x is the maximum-degree vertex, C an Eulerian tour of G∗ with the property that HCz contains a perfect matching for each z (such a C can be achieved by applying the bow-tie operations successively when needed). Denote C^x the family of heavy visits to x (that is, each element of C^x is of the form w,x,w, where w is a neighbor of x). By performing a series of bow-tie operations, we will transform each visit of C^x into a new visit containing three pairwise distinct terms.
To simplify notation we will still useC to denote the new Eulerian tour produced by applying an operation. If C^x≥2, choose a pair of visits p1,p2 of C^x, and apply bow-tie operation to C with regarding to p1,p2. Then in the new Eulerian tour Cp1,p2, the pair p1,p2 is transformed into two visits with each containing three pairwise distinct terms. Thus, each time of applying the bow-tie operation to C with regard to two elements of C^x deducts the number of C^x by two. Apply this operation until C^x≤1. If C^x=0, we are done. Suppose C^x=w,x,w. Let p=y,x,z be an arbitrary visit outside C^x. Apply the same operation to C with regard to w,x,w and p. Again, w,x,w can be eliminated without producing a new heavy visit. Eventually, we get an Eulerian tour, denoted again by C, of G∗ such that each element of Cx contains three pairwise distinct terms. Then in HCx, each visit of Cx is adjacent to Δ−2 arcs of Ax, and each arc of Ax is adjacent to Δ−2 visits of Cx. That is, HCx is a Δ−2-regular bipartite graph.
IfΔ=4, HCx is 2-regular, hence contains two distinct perfect matchings. Suppose that Δ≥5, and denote by M1,M2,…,Mi the set of all perfect matchings of HCx. Schrijver [9] states that every bipartite graph regular of degree k with 2n vertices contains at least k−1k−1/kk−2n perfect matchings. Thus, we have the following:(4)i≥Δ−3Δ−3Δ−2Δ−4Δ.
For every vertexu≠x in G, fix a perfect matching of HCu. As in the Proof of Theorem 1 in [7], a Hamilton cycle of XG can be derived from C by using the fixed perfect matchings of all bipartite graphs HCv with v≠x, together with every single perfect matching Mj of HCx, 1≤j≤i. Note that corresponding to distinct Mj, Mj′ of HCx, the derived Hamilton cycles of XG are also distinct. Therefore, XG has i different Hamilton cycles and the result follows.□
SupposeG is a graph containing no isolates. If XG is connected and 4-regular, then clearly G has a maximum degree of no less than 3. Hence by Theorem 1, we have the next result, which verifies Sheehan’s conjecture for 3-arc graphs.Corollary 1.
Every 4-regular 3-arc graph has no less than two Hamilton cycles.Proof of Theorem2.
SupposeG is a connected cubic graph and A,B an even IS-C decomposition of G. To simply notation, we employ B to represent the cactus induced by B.
SupposeG∗ is the multigraph achieved from G by doubling its all edges, B∗ the multigraph achieved from G∗ by deleting all edges joining some vertex of A. Equivalently, B∗ is the multigraph obtained from B by doubling each of its edges.
ThenB∗ is Eulerian. Assume C′ is an Eulerian tour of B∗ , so that C′x contains no heavy visit for each x∈B with 2 or 3 neighbors in B. Note that such a C′ can be obtained from any Eulerian tour of B∗ by applying a succession of bow-tie operations when necessary.
We next extendC′ to an Eulerian tour of G∗ as follows: for each vertex x∈B with degree 1 in B, let x′ be the only neighbor of x in B, and x1,x2 the other two distinct neighbors of x in A. Then C′x=x′,x,x′. We extend C′ at x to cover the four edges between x1,x2 and x such that the new visit decomposition at x is x′,x,x1,x1,x,x2,x2,x,x′. In other words, we insert the trail x,x1,x,x2,x into C′ via the midvertex of the visit x′,x,x′. For each vertex x∈B with degree 2 in B, let x1 be the unique neighbor of x in A, and x′,x′′ the other two distinct neighbors of x in B. Then C′x=x′,x,x′′,x′,x,x′′ by the assumption on C′. We extend C′ at x to cover the two edges between x1 and x such that the new visit decomposition is x′,x,x1,x1,x,x′′,x′,x,x′′. Applying this extension to every vertex of B that has degree 1 or 2, we obtain an Eulerian tour of G∗, denoted C.
By the wayC is extended, one may observe that Cx consists of no heavy visit if x∈B, and Cx contains only heavy visits if x∈A. In particular, the bipartite graph HCx is a set of three independent edges if x∈B, and HCx≅C6 if x∈A. Thus, in both cases HCx has a perfect matching, and, a Hamilton cycle of Xx, denoted by CX, can be derived from C.
SinceG is cubic, for each pair of adjacent a,b of G, by Definition 1, the subgraph Xa,b induced by vertices in Aa∪Ab in XG is isomorphic to K2,2.
For any two verticesa,b adjacent in B, let a1,a2 be two distinct neighbours of a other than b, and b1,b2 be two distinct neighbours of b other than a. Since each of Ca and Cb contains no heavy visit, we have Ca=a1,a,b,a2,a,b,a1,a,a2 and Cb=b1,b,a,b2,b,a,b1,b,b2. Let e1,e2 be parallel between a and b in B∗. Then each of e1,e2 is contained in a visit of Ca and a visit of Cb. Assume w.l.o.g. that a1,a,b,b1,b,a contain e1 and a2,a,b,b2,b,a contain e2. Then each of a1,a,b,b1 and a2,a,b,b2 is a segment of length 3 of C. We may define each of these two segments as a visit to the edge a,b of B, and denote them as a1,a,b,b1, a2,a,b,b2, respectively. From the definition of B∗, each edge, and hence a,b, of B is visited twice by C of B∗. Represent by Ca,b the set of two visits of C to the edge a,b, i.e., Ca,b=a1,a,b,b1,a2,a,b,b2.
Then, each element ofCa,b is a trail of length 3 which corresponds exactly to one edge of Xa,b covered by CX. And, the two visits of Ca,b are in fact corresponding to two independent edges of Xa,b, namely, aa2,bb2, aa1,bb1, which are covered by CX. This means that CX covers exactly one perfect matching (two independent edges) of Xa,b and leaves the other perfect matching uncovered by noting that Xa,b≅K2,2 contains two perfect matchings.
Apply the edge-shift operation (Definition3) to C with respect to the 2 parallel edges connecting a and b, denote the resulted trail(s) by C0. Then Ca,b is transformed into C0a,b=a1,a,b,b2,a2,a,b,b1. If C0 stays as an Eulerian tour of G∗, one can observe that any Hamilton cycle C0X, derived from C0, will cover the pair of independent edges of Xa,b which are not covered by CX.
The following claim shows that we can apply the edge-shift operations to every pair of parallel edges ofB∗ once and still get an Eulerian tour of G∗.
Claim. There are a series of edge-shift operations such that to every pair of parallel edges ofB∗ , exactly one operation is performed and the resultant trail is an Eulerian tour of G∗.
Proof of the Claim. First consider an edgex,y belonging to none of the cycles of B, then x,y is a bridge of B. Let e1,e2 be the two parallel edges between x and y in B∗. Then the orientations of e1,e2 are opposite to each other in C, by (1) of Remark 2, CC;e1,e2 stays as an Eulerian tour of B∗. Thus, we can apply the edge-shift operation to each pair of parallel edges of B∗ joining two end-vertices of a bridge of B. To simplify notation, denote again by C the Eulerian tour of B∗ after processing all such pairs of parallel edges.
Next we process edges on cycles in the cactusB. Since ΔB≤3, any two distinct cycles in B are vertex- and edge-disjoint. We process these cycles one by one.
LetL=x1,x2,…,xl,x1 be an arbitrary cycle of B, where l≥4 is even. Since every vertex has degree 3 in G, each xj has a neighbor, denoted by xj′, where 1≤j≤l. Note that each edge xj,xj′ is a bridge of B. Denote by Lj the component containing xj′ after deleting the edge xj,xj′. If C proceeds along some visit xj±1,xj,xj′ into Lj, C must return back to the component containing the cycle L via the visit xj′,xj,xj∓1 immediately after C finishing its all traverses in Lj. We can shrink the traverse of C in Lj as a simple visit to xj as follows: suppose C proceeds its traverses in Lj using the following trail:(5)T′:xj−1,xj,xj′,…,xj′,xj,xj+1.
We can first shrink this trail into the visitxj−1,xj,xj+1 to xj, and this visit could be restored back to its original form T′ above after the processing of the edges of L. After shrinking all such traverses of C in Li, where 1≤j≤l, we get an Eulerian tour C˜ of the multigraph L∗ (L∗ is the multigraph obtained from the cycle by doubling each of its edges). Equivalently, C˜ is a single walk that covers each edge of the simple cycle L twice. Then, for each edge ej:=xj,xj+1 of L, denoted by ej,ej′, the two parallel edges between xj and xj+1.
Apply the edge-shift operation toC˜ with respect to ej,ej′. Since the orientations of ej,ej′ in C˜ are the same, CC˜;ej,ej′ is a set of two closed trails, C1, C2, say. One can observe that the trail covering ej+1 and that covering ej+1′ are distinct, where ej+1, ej+1′ are two parallel edges between xj+1 and xj+2. After this operation, we immediately apply the edge-shift operation to C1, C2 with respect to ej+1, ej+1′. Then, this operation will concatenate C1 and C2 together, that is, C (C1,C2;ej+1, ej+1′) will become again an Eulerian tour of L∗.
Continue applying this operation to the pairsej+2,ej+2′,ej+3,ej+3′,…,ej−1,ej−1′ej+2,ej+2′,ej+3,ej+3′,…,ej−1,ej−1′; we finally obtain an Eulerian tour of L∗, denoted again by C^. Then we restore C^ back to an Eulerian tour of B∗.
Using this procedure to process all cycles ofB, we finally obtain an Eulerian tour of G∗ after performing exactly one operation to every pair of parallel edges of B∗. The claim follows.□
Denote byC¯, the Eulerian tour of G∗ produced after applying the edge-shift operation exactly once to each pair of parallel edges connecting two adjacent vertices of B.
Consider every edgee with one end-vertex x∈A (then e is not in B). Then all neighbours of x lie in B. Denote Nx=x1,x2,x3, e=x,x1 and Nx1=x,z,z′, where x1,x2,x3∈B. Then, by the construction of C,(6)Cx=x1,x,x1,x2,x,x2,x3,x,x3.
InXx1,x, such a heavy visit x1,x,x1 is exactly corresponding to two adjacent edges of Xx1,x. For example, in this instance, if C enters x via z,x1 and leaves via x1,z′ to complete the visit x1,x,x1x1,x,x1; then, it 1-1 corresponds to the two edges x1z′,xt,xt,x1z , which is a 2-path in Xx1,x (also in the Hamiltonian cycle CX), where t is either x2 or x3. Note that the other two edges in Xx1,x uncovered by CX will be available in the second Hamilton cycle C¯X.
We do not apply any operation on edgese=x,x1 with one end-vertex in A. We can just use the two uncovered edges in the new Hamilton cycle when constructing it. Equivalently, for each x∈A, the perfect matching HC¯x employed in deriving C¯X is the one that shares no common edge with HCx.
Then,C¯X is a Hamilton cycle sharing no edges with CX, the proof is completed.□Corollary 2.
SupposeG is cubic. If G has a stable set such that whose removal leaves G a tree, then XG has a Hamiltonian decomposition.Since every cubic graph has an IS-C decomposition, every bipartite cubic graph has an even IS-C decomposition. We have the following.Corollary 3.
The 3-arc graph of any bipartite cubic graph has a Hamiltonian decomposition.LetP be the Petersen graph. It is not difficult to find a stable set of P consisting of three vertices whose removal leaves P a tree. Let G be an n-prism, n≥3. Then, G is isomorphic to the Cartesian product Cn□K2. Denote VG=VC∪VC′, where VC=v1,v2,…,vn, VC′=v1′,v2′,…,vn′, and, each of VC and VC′ induces an n-cycle. The edge set of G is EC∪EC′∪vi,vi′:i=1,2,…,n. Set S:=v2j:j=1,2,…,⌊n/2⌋. If n is even, then S,VG−S is an even IS-C decomposition of G with VG−S inducing a unicyclic graph; if n is odd, then S∪v1′,VG−S∪v1′ is an even IS-C decomposition of G with VG−S∪v1′ inducing a tree. By applying 2 and 3, we obtain the following example:Example 1.
(1) The 3-arc graph of Petersen graph has a Hamiltonian decomposition; (2) The 3-arc graph of then-prism has a Hamiltonian decomposition.Remark 3.
The condition in Theorem2 is sufficient but not necessary. For example, K4 does not have an even IS-C decomposition but XK4 is still Hamiltonian decomposable. In XK4, see Figure 1, each of the two sets of bold edges (in color black) and thin edges (in color blue) forms a Hamilton cycle [10].



---

*Source: 5837405-2022-04-28.xml*