# Hamilton-Connected Mycielski Graphs∗

Authors: Yuanyuan Shen; Xinhui An; Baoyindureng Wu
Journal: Discrete Dynamics in Nature and Society
 (2021)

---

## Abstract

Jarnicki, Myrvold, Saltzman, and Wagon conjectured that ifG is Hamilton-connected and not K2, then its Mycielski graph μG is Hamilton-connected. In this paper, we confirm that the conjecture is true for three families of graphs: the graphs G with δG>VG/2, generalized Petersen graphs GPn,2 and GPn,3, and the cubes G3. In addition, if G is pancyclic, then μG is pancyclic.


---

## Body

## 1. Introduction

All graphs considered in this paper are simple and finite. For notations and terminologies not defined here, we refer to Bondy and Murty [1]. A spanning cycle (path) of a graph is called Hamilton cycle (Hamilton path). A graph which contains a Hamiltonian path between every two vertices of G is called Hamilton-connected (HC). Mycielski [2] proved that the chromatic numbers of triangle-free graphs can be arbitrarily large by introducing a graph transformation as follows. For a graph G on vertices V=v1,v2,…,vn, its Mycielski graph, denoted by μG, is the graph on vertices X∪Y∪z=x1,x2,…,xn∪y1,y2,…,yn∪z with edges zyi for all i and edges xixj, yixj, and xiyj for all edges vivj in G. In recent years, a number of papers are devoted to various properties of Mycielski graphs, such as Hamilton-connectivity, Hamiltonicity [3–7], total chromatic number [8, 9], circular chromatic number [10–14], and connectivity [15, 16]. Fisher et al. [4] obtained the following results.Theorem 1 (see Fisher et al. [4]).
The following results hold for a graphG:(1)
IfG is Hamiltonian, then μG is Hamiltonian(2)
IfG is not connected, then μG is not Hamiltonian(3)
IfG has at least two pendant vertices, then μG is not Hamiltonian
Cheng, Wang, and Liu studied Hamiltonicity and Hamilton-connectedness in Mycielski graphs of bipartite graphs.Theorem 2 (see Cheng et al. [3]).
For a bipartite graphG, the following are true:(1)
IfμG is Hamiltonian, then G is balanced(2)
IfμG is Hamiltonian, then G has a Hamilton path
In 2017, Jarnicki et al. [17] established the following results for μG being Hamilton-connected or not.Theorem 3 (see Jarnicki et al. [17]).
The following results hold for a graphG:(1)
IfG is an odd cycle, then μG is Hamilton-connected(2)
IfG is a Hamilton-connected graph with order odd, then μG is Hamilton-connected(3)
IfG is an even cycle, then μG is not Hamilton-connected
They posed the following conjecture.Conjecture 1 (see Jarnicki et al. [17]).
IfG is Hamilton-connected and not K2, then μG is Hamilton-connected.
In this paper, we confirm that the conjecture is true for three families of graphs: the graphsG with δG>VG/2, generalized Petersen graphs GPn,2 and GPn,3, and the cubes G3. In addition, if G is pancyclic, then μG is pancyclic.


## 2. Mycielski Factor

LetG be a connected graph of order n even, and v1∈VG. We call a connected spanning subgraph of G to be a Mycielski factor starting at v1 if it consists of an even number of odd cycles C1,…,C2s (possibly s=0) and an even cycle C2s+1 with the chord (possibly empty), joined by 2s edges e1,…,e2s, where ei=vi′vi+1 for each i∈1,…,2s such that vivi′∈VCi for each i∈1,…,2s+1, and the chord joins v2s+1′ and a vertex at distance even on C2s+1.Lemma 1.
Assume that a graphG is Hamilton-connected. If, for any v∈VG, there exists a Mycielski factor starting at v, then μG is Hamilton-connected.Proof.
As in the assumption, letG be HC. Trivially, G has a Hamilton cycle. By Theorem 3 (2), μG is HC if the order of G is odd. So, it remains to tackle the case when the order is even. Let VG=v1,…,v2n, where n≥2. Recall that VμG=X∪Y∪z. Take any two vertices A,B∈VμG. We consider five cases in terms of the location of A and B in X,Y, and z.Case 1.
A∈X and B∈X.
Without loss of generality, letA=x1 and B=x2n. Since G is HC, there exists a Hamilton path P connecting v1 and v2n in G. We shall find a Hamilton path of μG depending on P as follows. Zigzag up from x1 until y2n is reached. Then, jump via z to y1, and zigzag right until x2n is reached. Formally, it is(1)x1−y2−x3−⋯−y2n−z−y1−x2−⋯−x2n,as shown in Figure 1.Figure 1
A Hamilton path fromA to B.Case 2.
A∈Y and B∈Y.
Without loss of generality, letA=y1 and B=y2n. Since G is HC, there exists a Hamilton path P connecting v1 and v2n in G. Thus, there exists a neighbor, say v2, of v1. Zigzag up from y1 to x2 and then back to x1, zigzag up to x2n−1 and then up to x2n, and zigzag left to y3 and then up to z and y2n, as shown in Figure 2. Formally,(2)y1−x2−x1−y2−⋯−x2n−1−x2n−y2n−1−x2n−2⋯−−y3−z−y2n.Figure 2
A Hamilton path fromA to B.Case 3.
A∈XandB∈Y.
Without loss of generality, letA=x1 and B=y2n. Since G is HC, there exists a Hamilton path P connecting v1 and v2n in G. We are able to find a Hamilton path joining A and B: zigzag up from x1 to x2n−1 and then up to x2n, and zigzag left to y1, and then reach z and y2n, as shown in Figure 3. Formally, it is(3)x1−y2−x3−⋯−x2n−1−x2n−y2n−1−⋯−y1−z−y2n.Figure 3
A Hamilton path fromA to B.Case 4.
A∈YandB=z.
Without loss of generality, letA=y1. Since G is HC, G has a Hamilton cycle C. Label the vertices of C as v1v2,…,v2nv1. We are able to find a Hamilton path joining A and B: zigzag from y1 to x2n and then go to x1, and then zigzag right to y2n, and finish at z, as shown in Figure 4. Formally, it is(4)y1−x2−y3−⋯−x2n−x1−y2−⋯−y2n−z.Figure 4
A Hamilton path fromY to z.Case 5.
A∈XandB=z.
Without loss of generality, letA=x1. Let H be a Mycielski factor of G starting at v1, which consists of an even number of odd cycles C1,…,C2s (possibly s=0) and an even cycle C2s+1 with the chord (possibly empty), joined by 2s edges e1,…,e2s, where ei=vi′vi+1 for each i∈1,…,2s such that vivi′∈VCi for each i∈1,…,2s+1, and the chord joins v2s+1′ and a vertex at distance even on C2s+1.
Ifs≥1, for every integer i∈1,…,2s, label the vertices of Ci in the clockwise order u1u2,…,u2k+1. One can find a Hamilton path Pi of μCi as follows:(5)x1y2x3y4,…,x2k+1,y1x2y3x4,…,y2k+1,where u1=vi and u2k+1=vi′.
LetC2s+1=w1w2⋯w2l be an even cycle with chord w2lw2t in H. One can find a Hamilton path P2s+1 of μCi as follows:(6)x1y2x3y4,…,y2l,x2ty2t+1x2t+2,…,x2l,y1x2y3x4,…,y2t−1,where w1=vi and w2l=vi′.
Thus,∪i=12s+1Pi∪vivi′:1≤i≤2s∪y2t−1z is a Hamilton path of μG from joining x1 and z.


## 3. Hamiltonian Connectedness

Theorem 4.
Assume thatG is a Hamilton-connected graph of order n≥3. If δG≥n/2+1, then μG is Hamilton-connected.Proof.
Letv be a vertex of G. We consider a Hamilton cycle C of G. Let u be a neighbor of v on C. Since du≥n/2+1, it has a neighbor at distance even on C. By Lemma 1, μG is HC.
Thekth power of a graph G, denoted by Gk, is a graph with the same vertex set as G in which two vertices are adjacent if and only if their distance in G is at most k. Thus, G1=G. We need the following result due to Karaganis [18].Theorem 5 (see Karaganis [18]).
The cubeG3 of every connected graph G of order n≥3 is Hamilton-connected.Theorem 6.
For any connected graphG of order n≥3, μG3 is Hamilton-connected.Proof.
By Theorem5, G3 is HC for G. Since μH3 is a spanning subgraph of μG3 for any spanning graph H of G, to show μG3 is HC, it suffices to show that μT3 is HC for any tree T of order n≥3. Since T3 is HC, by Theorem 3 (1), we may assume that n is even. By Lemma 1, it remains to show that T3 has a Mycielski factor starting from each vertex v∈VT.
Letw be a neighbor of v in T, and let Tv and Tw be the components of T−vw containing v and w, respectively. Let nv and nw be the order of Tv and Tw, respectively. Let v′ be a neighbor of v in Tv, and let w′ be a neighbor of w in Tw.Case 1: bothnv and nw are at least 3.Subcase 1.1: bothnv and nw are odd.By Theorem5, both Tv3 and Tw3 are HC. Let Cv and Cw be Hamilton cycles of Tv and Tw, respectively. One can see that Cv∪Cw+v′w is a Mycielski factor of T3 starting at v.Subcase 1.2: bothnv and nw are even.By the induction hypothesis,Tv3 has a Hamilton path Pvv′ joining v and v′, and Tw3 has a Hamilton path Pww′ joining w and w′. One can see that Pvv′∪Pww′+vw+v′w′+v′w is a Mycielski factor of T3 starting at v.Case 2:minnv,nw≤2.Subcase 2.1:minnv,nw=nv≤2.Subcase 2.1.1:minnv,nw=nv=1.Sincenv+nw=n is an even number at least 3, nw is an odd number at least 3. By Theorem 5, let Cww′ be a Hamilton cycle of Tw3 containing ww′. It is easy to see that Cww′+vw+vw′ is a Mycielski factor of T3 starting at v.Subcase 2.1.2:minnv,nw=nv=2.Ifnw=2, then n=4. Trivially, Tw3=K4 has a Mycielski factor starting at v.Ifnw≠2, then nw is an even number at least 4. By Theorem 5, let Pww′ be a Hamilton path of Tw3. It can be seen that Pww′+vw+w′v′+v′w is a Mycielski factor starting at v.Subcase 2.2:minnv,nw=nw≤2.
IfT≅K1,n−1, then T3≅Kn has a Mycielski factor starting at v. Next, we assume that T≇K1,n−1. We can choose a neighbor w of v such that nw≥2. Combining with our assumption that minnv,nw=nw≤2, we have nw=2. By Theorem 5, let Pvv′ be a Hamilton path of Tv3. It can be checked that Pvv′+vw+ww′+v′w′+v′w is a Mycielski factor starting at v.
In 1969, Watkins [19] introduced the notion of the generalized Petersen graph GPn,k, 1≤k≤n, as follows. The vertex set is ui,vi:1≤i≤n, and the edge set is uiui+1,vivi+k,uivi, where the subscript arithmetic performs modulo n using the residues 1,…,n. In 1971, Frucht et al. [20] showed that GPn,k is vertex-transitive if and only if k2≡±1modn or n,k=10,2. Next, we consider the Hamilton-connectedness of the Mycielski graph of the generalized Petersen graphs GPn,2 and GPn,3.Theorem 7 (see Alspach and Liu [21]).
The generalized Petersen graphGPn,2 with n≥6 is Hamilton-connected if and only if n≡1,2,3mod6.Theorem 8.
IfGPn,2 is Hamilton-connected for n≥6, then μGPn,2 is Hamilton-connected.Proof.
In view of Lemma1, it suffices to show that GPn,2 has a Mycielski factor starting at any v∈VGPn,2. We consider two cases:Case 1:n≡1or3mod6.Sincen is odd, GPn,2 is vertex-transitive, and we may assume that v=u1, without loss of generality. Let C1 and C2 be the outer cycle and inner cycle of GPn,2. Let v be a vertex of GPn,2. It is clear that C1∪C2+u2v2 is a Mycielski factor of GPn,2 starting at v.Case 2:n≡2mod6.
By the symmetry, it suffices to tackle two possibilities according to the location ofv in GPn,2: v lies on the outer cycle or inner cycle of GPn,2. Without loss of generality, let v=u1 or v=v1.
First, for the case whenn=8, we can find a Mycielski factor Fn of GPn,2 as follows:(7)F8=C8+u2u3ifv=u1,C8+u1u2ifv=v1,where(8)C8=u1v1v3u3u4v4v6u6u5v5v7u7u8v8v2u2ifv=u1,v1v3u3u2v2v4u4u5v5v7u7u6v6v8u8u1ifv=v1.
Forn=14, by inserting 12 new vertices to C8 of F8, we get C14 as illustrated in Figures 5–7 for the case that v lies in the outer cycle and for the case that v lies in the inner cycle as illustrated in Figures 6, 8, and 9. For the case when n≥20, by inserting 12 new vertices to Fn−6 with type A insertion, we obtain a Mycielski factor Fn of GPn,2 starting at v.Figure 5
F8 from u1 to u2 in GP8,2.Figure 6
TypeA insertion.Figure 7
F14 obtained from F8 by type A insertion in GP8,2.Figure 8
F8 from v1 to u1 in GP8,2.Figure 9
F14 obtained from F8 by type B insertion in GP8,2.Theorem 9 (see Alspach and Liu [21]).
The generalized Petersen graphGPn,3 with n≥6 is Hamilton-connected if and only if n is odd.Theorem 10.
IfGPn,3 is Hamilton-connected, then μGPn,3 is Hamilton-connected.Proof.
SinceGPn,3 is Hamilton-connected, by Theorem 9, n is an odd number at least 7. Let v be a vertex of GPn,3. In view of Lemma 1, it suffices to show that GPn,3 has a Mycielski factor starting at v. We consider two cases:Case 1:n≡1or5mod6.Sincen is odd, GPn,3 is vertex-transitive; by the symmetry, we may assume that v=u1, without loss of generality. Let C1 and C2 be the outer cycle and inner cycle of GPn,3. It is clear that C1∪C2+u2v2 is a Mycielski factor of GPn,3 starting at v.Case 2:n≡3mod6.
By the symmetry, it suffices to tackle two possibilities according to the location ofv in GPn,3: v lies on the outer cycle or inner cycle of GPn,3. Without loss of generality, let v=u1 or v=v1.
First, for the case whenn=9, we can find a Mycielski factor Fn of GPn,3 starting at v as follows:(9)F9=C9+v1v7ifv=u1,C9+u1u9ifv=v1,where C9=u1u2v2v5v8u8u9v9v6v3u3u4u5u6u7v7v4v1.
Forn=15, by inserting 12 new vertices to C9 of F9, we get C15 as illustrated in Figures 10–12. For the case when n≥21, by inserting 12 new vertices to Fn−6 with type B insertion, we obtain a Mycielski factor Fn of GPn,3 starting at v.Figure 10
F9 from u1 to v1 in GP9,3.Figure 11
TypeB insertion.Figure 12
F15 obtained from F9 by type B insertion in GP9,3.


## 4. Pancyclicity

In this section, we show that if a graphG is pancyclic, then μG is also pancyclic.Theorem 11.
IfG is pancyclic, then μG is pancyclic.Proof.
LetG be a pancyclic graph of order n. Since μG contains G as its subgraph, μG contains a cycle of length l for each l∈3,…,n.
Now, we find a cycle of lengthn+1 in μG. Take a cycle C of length n−2 in G. Without loss of generality, let P=v1v2,…,vn−2 be a path resulting from C deleting an edge. It can be seen that x1x2,…,xn−2y1zyn−2x1 is a cycle of length n+1, as illustrated in Figure 13. In a similar way, one can find a cycle of length n+2 in μG in terms of a cycle of length n−1 in G.
Next, we will find a cycle of lengthn+k in μG for each k∈3,…,n+1. Take a Hamilton cycle C. Without loss of generality, let C=v1v2,…,vnv1 in G. We consider two cases according to the parity of k:Case 1:k is odd.One can find a cycle of lengthn+k in μ(G), as shown in Figure 14. Formally, it is(10)x1−y2−x3−⋯−yk−1−z−y1−⋯−xk−1−xk−⋯−xn−x1.Case 2:k is even.
Zigzag up fromx1 to xk−1 and left to xk−2, then zigzag left to y1, z, yk−1, and xk, and go right to xn and back to x1, as shown in Figure 15. Formally, it is(11)x1−⋯−xk−2−xk−1−yk−2−⋯−y1−z−yk−1−xk−⋯−xn−x1.Figure 13
Finding a cycleCn+1 in μG from a cycle Cn−2 in G.Figure 14
A cycle of lengthn+k in μG if k is odd.Figure 15
A cycle of lengthn+k in μG if k is even. □


## 5. Conclusion

In this paper, we introduce the notion of the Mycielski factor of a graph. If a graphG has a Mycielski factor starting at v for any v∈VG, then μG is Hamilton-connected. Applying this result, we are able to show that if a graph G belongs to three (well-defined) families of graphs, then μG is Hamilton-connected. However, the full conjecture of Jarnicki, Myrvold, Saltzman, and Wagon is not yet solved. We also prove that if G is pancyclic, then μG is pancyclic.One of the reviewers proposed the following two interesting problems.Zhong et al. [7] showed that the line graph of the generalized Petersen graph GPn,k is always Hamilton-connected. Is it easy to show that the Mycielski graph of LGPn,k is Hamilton-connected?It is known that the line graph of a Hamilton-connected graphG is also Hamilton-connected. Is μLG Hamilton-connected if LG is Hamilton-connected? [22].



---

*Source: 3376981-2021-09-15.xml*