# On the Circumference of 3-Connected Cubic Triangle-Free Plane Graphs

Authors: Adthasit Sinna; Witthawas Phanthawimol; Sirirat Singhun
Journal: Journal of Mathematics
 (2021)

---

## Abstract

The circumference of a graphG is the length of a longest cycle in G, denoted by cirG. For any even number n, let cn  = min {cirG|G is a 3-connected cubic triangle-free plane graph with n vertices}. In this paper, we show that an upper bound of cn is n+1−3⌊n/136⌋ for n≥136.


---

## Body

## 1. Introduction

Graph theory has applications in various research areas. In chemistry and biology, it gives an illustration of molecular structures in [1, 2], and it identifies interactions between humans and nature in [3]. Graph theory can be combined together with other branches of mathematics such as algebraic graph theory, matroid theory, graph labeling, and topological graph theory. Recently, it is combined with fixed point theory in [4, 5].We consider only simple undirected graph. LetG = (VG, EG) be a graph, where VG is the vertex set of G and EG is the edge set of G. The degree of a vertex v is the number of edges incident to v. A graph is cubic if all vertices have degree exactly three. A plane graph is a graph embedded in a plane without edge crossing. An xy-path of a graph G is a sequence of distinct vertices x=v0,v1,v2,…vn=y of G such that vivi+1∈EG, for all i∈0,1,2,…,n−1. Similar to xy-path, a cycle of a graph G is defined as a sequence of distinct vertices u1,u2,…,um, u1 of G such that umu1, ujuj+1∈EG, for all j∈1,2,…,m−1. The triangle is a cycle of length 3, and a graph is triangle-free if it contains no triangle. A graph G is connected if there is a uv-path for all distinct u,v∈VG. A graph G is k-connected if VG≥k, and for any X⊆VG of size k−1, a graph G−X is connected. A k-leg fragment H is a connected plane graph such that there are exactly k vertices of H with degree two, and the remaining vertices have degree three. A Hamilton cycle of a graph G is a cycle containing all vertices of G.Finding Hamilton cycles in graphs is a famous topic in graph theory. In 1880, Tait [6] conjectured that a 3-connected cubic plane graph has a Hamilton cycle. Tutte [7] constructed the Tutte fragment, a triangle-free 3-leg fragment with 15 vertices, and showed the following statement.Lemma 1 (see [7]).
LetT be the Tutte fragment in Figure 1. Then,(i)
There is anxy-path (respectively, an xz-path) containing all vertices of H, and(ii)
For eachyz-path P, VP≤14, i.e., P misses at least one vertex from T.Figure 1
The Tutte fragment.Using three Tutte fragments and one vertex, the Tutte graph is the first counterexample of Tait’s conjecture with 46 vertices. Later, Holton and McKay [8] showed that a smallest counterexample of this conjecture is the Barnette–Horák–Lederburg graph, a 38-vertex triangle-free graph containing two Tutte fragments. Moreover, Grinberg graph [9] and Faulkner–Younger graph [10] are other counterexamples of this conjecture without any Tutte fragment.For 4-connected graphs embedded in surfaces, Tutte [11] proved that every 4-connected plane graph has a Hamilton cycle. Extending Tutte’s result, Thomas and Yu [12] proved that every 4-connected projective plane graph has a Hamilton cycle. In the case of toroidal graph, Grünbaum [13] and Nash-Williams [14] independently conjectured that every 4-connected toroidal graph has a Hamilton cycle. For the closest result of this conjecture, Thomas and Yu [15] proved that every 5-connected toroidal graph has a Hamilton cycle. A closed knight’s tour on the chessboard is an example of Hamilton cycle problem. Some results of a closed knight’s tour are shown in [16, 17].Define the circumference of a graphG as the length of a longest cycle in a graph G, denoted by cirG. Since Tait’s conjecture is false, the generalized question is what is the minimum circumference of any 3-connected cubic (triangle-free) plane graph with n vertices? Then, let bn=min{cirG|G is a 3-connected cubic plane graph with n vertices} and cn=min {cirG|G is a 3-connected cubic triangle-free plane graph with n vertices}.Note thatbn≤cn, and n must be even because the sum of degrees of all vertices is even. For the exact value of cn, Holton and McKay [8] showed that bn=cn=n if n≤36, and b38=c38=37. Note that cn is still unknown for n≥40.For a lower bound ofbn, Jackson [18] showed that an n-vertex 3-connected cubic graph has circumference Ωn0.694 for sufficiently large n. Bilinski et al. [19] improved this to Ωn0.753, and then, Liu et al. [20] improved to Ωn0.8. This implies bn≥Ωn0.8 for sufficiently large n.For an upper bound ofbn for all even numbers n≤38. Let Gi be the sequence of graphs such that G1 is the the Barnette–Horák–Lederburg graph, and Gi+1 is obtained from Gi by replacing all vertices of Gi by triangle. Then, Gi is a 383i−1-vertex graph with circumference 373i−1. Note that a longest cycle of Gi misses 3i−1 vertices. Let H be a graph obtained by Gi by replacing k vertices of Gi by triangle, where k<VGi. Then, cirH≤VH−3i−1. This gives bn≤n−3i−1 if 383i−1≤n≤383i−2.For a triangle-free graph, Lu [21] constructed a 4k+74k′+2-vertex graph, where k≥2 and k′≥1, with circumference 4k+74k′+2−min4k+8,4k′−2. If k′=k+3, then this graph implies cn≤n−n+49/4+5/2 for infinitely many integers n. Next, Lo and Schmidt [22] constructed a 122m-vertex graph with circumference at most 120m for some positive integer m. This implies cn≤60n/61 for some n which are divisible by 122.In this paper, we show that an upper bound ofc136 is 133 in Theorem 1, and the graph Gk, a 136k-vertex graph, has the circumference 133k+1 in Lemma 4. In Theorem 2, we improve an upper bound of cn to n+1−3⌊n/136⌋, for all n≥138.


## 2. Main Results

First, we construct the 4-leg fragmentH with 136 vertices as in Figure 2(a). Note that H is triangle-free and contains nine Tutte fragments. Next, for any positive integer i, we let Hi be a copy of H such that ai, bi, ci, and di correspond to a, b, c, and d in H, respectively. Finally, we construct a graph Gk from the union of graphs H1,H2,…,Hk, by adding edges bka1, dkc1, biai+1, and dici+1, for all i∈1,2,…,k−1, as in Figure 3. Note that Gk is a 3-connected cubic triangle-free plane graph with 136k vertices.Figure 2
(a) The 4-leg fragmentH. (b) The graph M obtained from H by contracting all Tutte fragments into vertices.
(a)(b)Figure 3
The graphGk.By the construction ofGk, a longest cycle C of Gk, where k≥2, must pass through some fragments Hi. Since Hi is a 4-leg fragment, C∩Hi are either an xy-path, where x, y∈ai,bi,ci,di, or a union of two disjoint paths where all end vertices of these paths are in ai,bi,ci,di. In order to find the circumference of Gk, it is necessary to show the maximum size of each path of H in Lemma 2 and of each union of two disjoint paths of H in Lemma 3.Lemma 2.
LetH be the 4-leg fragment in Figure 2(a). Then,(i)
Eachab-path in H contains at most 130 vertices(ii)
Eachac-path (respectively, bd-path) in H contains at most 132 vertices(iii)
Eachad-path (respectively, bc-path) in H contains at most 133 vertices(iv)
Eachcd-path in H contains at most 119 verticesProof.
LetM be the graph obtained from H by contracting all Tutte fragments into vertices A1, A2, A3, B1, B2, B3, C1, C2, and C3 as in Figure 2(b). Note that VM=10 and, the vertices a, b, c, and d of H belong to the fragments represented by A3, B2, C2, and C3, respectively. Let P be a longest xy-path, where x,y∈a,b,c,d, and let Q be a path of M corresponding to P. So, Q is the uv-path, where u,v∈A3,B2,C2,C3. Note that if Q passes through all vertices in VM−w, then VH−VP≤10, i.e., P may miss the vertex w and one vertex from each Tutte fragments. Otherwise, VH−VP≥15. Then, VQ−w should be the maximum in M. Thus, we consider four cases as follows.Case 1:P is an ab-path. Then, Q is an A3B2-path. If w∈Q, then either C2∈Q or C3∈Q. Suppose w∈Q. Since there is only one A3B2-path missing only vertex w, the sequence of vertices of Q is A3, A1, A2, C2, C1, C3, B3, B1, and B2. This implies P passes through each fragment in this order. By Lemma 1, P misses vertex w and other five vertices from the fragments A1, B1, C1, C2, and C3. Then, VP=130.Case 2:P is an ac-path, or a bd-path. By the symmetry of H, we consider only ac-path. Since there is only one A3C2-path containing all vertices of M, the sequence of vertices of Q is A3, A2, A1, w, B1, B2, B3, C3, C1, and C2. By Lemma 1, P misses four vertices from the fragments A2, B2, C1, and C3. Then, VP=132.Case 3:P is an ad-path, or a bc-path. By the symmetry of H, we consider only ad-path. Since there is only one A3C3-path containing all vertices of M, the sequence of vertices of Q is A3, A1, A2, C2, C1, w, B1, B2, B3, and C3. By Lemma 1, P misses three vertices from the fragments A1, B2, and C2. Then, VP=133.Case 4:P is a cd-path. Then, Q is a C2C3-path. If C1∈Q, then either A1,A2,A3⊆Q or B1,B2,B3⊆Q. Suppose C1∈Q. Since there is only one C2C3-path missing only vertex C1, the sequence of vertices of Q is C2, A2, A3, A1, w, B1, B2, B3, and C3. Note that Q misses the vertex C1 so P misses 15 vertices from fragment C1. By Lemma 1, P misses other two vertices from the fragments A3 and B2. Then, VP=119.For a union of two disjoint paths, we define awx,yz-dual path as the disjoint union of a wx-path and a yz-path. Note that the intersection of an ad-path and a bc-path in H is not empty. By the symmetry of H, there are exactly two cases of wx,yz-dual path, where w,x,y,z=a,b,c,d in H as follows.Lemma 3.
LetH be the 4-leg fragment in Figure 2(a). Then,(i)
Eachab,cd-dual path in H contains at most 133 vertices(ii)
Eachac,bd-dual path in H contains at most 134 verticesProof.
LetM be the graph defined from H in Figure 2(b). Let D be the largest wx,yz-dual path in H such that w,x,y,z=a,b,c,d. Let DM be the dual path corresponding to D. Without loss of generality, we consider two cases as follows:Case 1:D is an ab,cd-dual path. Then, DM is an A3B2,C2C3-dual path. Since there is exactly one dual path containing all vertices of M, the sequences of these two paths of DM are A3, A2, A1, w, B1, B3, B2, and C2, C1, C3, respectively. By Lemma 1, D misses three vertices from the fragments A2, B3, and C1. Then, VD=133.Case 2:D is an ac,bd-dual path. Then, DM is an A3C2,B2C3-dual path. Without the loss of generality, there is only one dual path containing all vertices of M. Then, the sequences of these two paths of DM are A3, A2, A1, w, C1, C2, and B2, B1, B3, C3, respectively. By Lemma 1, D misses two vertices from the fragments A2 and B1. Then, VD=134.Since we obtain Lemma2 and Lemma 3, we have c136≤133 by showing the following theorem.Theorem 1.
There is a 136-vertex 3-connected cubic triangle-free plane graph with circumference 133.Proof.
LetK be a graph obtained from the fragment H by adding edges ac and bd (see Figure 4(a)). Note that K is a 3-connected cubic triangle-free plane graph with 136 vertices. Let M′ be the graph obtained from K by contracting all Tutte fragments into vertices A1, A2, A3, B1, B2, B3, C1, C2, and C3 as in Figure 4(b).
LetC be a longest cycle of K satisfying the condition in each following case.Figure 4
(a) The graphK. (b) The graph M′ obtained from K by contracting all Tutte fragments into vertices.
(a)(b)Case 1.
Neitherac nor bd is in C. Let D be the cycle of M′ corresponding to C. Then, neither A3C2 nor B2C3 is in D. If w∈VD, then either VD=A1,A2,A3 or VD=B1,B2,B3. Suppose w∈VD. Since there is only one cycle containing all vertices of M′, the sequence of vertices of D is w, A1, A3, A2, C2, C1, C3, B3, B2, B1, and w. By Lemma 1, C misses five vertices from the fragments A3, B2, C1, C2, and C3. Then, VC=131.Case 2.
Only one edge fromac,bd is in C. Assume without loss of the generality that ac∈EC, but bd∈EC. Then, C−ac is an ac-path in H. By Lemma 2 (ii), VC=VC−ac=132.Case 3.
Bothac and bd are in C. Then, C−ac,bd is an ab,cd-dual path in H. By Lemma 3(i), VC=VC−ac,bd=133.
Comparing the length ofC in each case, we conclude that cirK=133.Recall that a graphGk has 136k vertices. Then, we give the circumference of Gk as follows.Lemma 4.
The circumference ofGk is 133k+1 for all positive integers k.Proof.
Fork=1, we use the similar proof to Theorem 1 to show that cirG1  = 134. Suppose k≥2. Let C be a longest cycle of Gk passing through all fragments H1,H2,H3,…,Hk. Without loss of generality, we generate each case by the possible cases of C∩H1 as follows. Case 1:C∩H1 is an xy-path, where x∈a1,c1 and y∈b1,d1.Then,C∩Hi is an xy-path, where x∈ai,ci and y∈bi,di, for any i∈2,3,…,k (see Figure 5(a)). By Lemma 2, C∩Hi≤133. This implies VC≤133k.Case 2:C∩H1 is either a b1d1-path or an a1c1-path. Assume without loss of generality that C∩H1 is a b1d1-path. Then, C∩Hk is an akck-path, and C∩Hi is an aibi,cidi-dual path, for any i∈2,3,…,k−1 (see Figure 5(b)). By Lemma 2(ii) and Lemma 3(i), VC=2132+133k−2=133k−2.Case 3:C∩H1 is an a1c1,b1d1-dual path. Then, C∩Hi is an aibi,cidi-dual path, for any i∈2,3,…,k. Note that bka1, dkc1, biai+1, dici+1∈EC, for all i=1,2,…,k−1 (see Figure 5(c)). By Lemma 3, VC=134+133k−1=133k+1.
For the case that a longest cycleD does not intersect some fragments Hi, we can assume, without loss of generality, that D∩Hi≠∅ if 1≤i≤m, otherwise D∩Hi=∅ (see Figure 5(d)). This case is similar to Case 2, so we can show that VD=2132+133m−2  =  133m−2≤133k−2.
Then, we conclude that a longest cycle inGk is a cycle defined in Case 3 which implies that cirGk=133k+1.Figure 5
Cycles in Lemma4. (a) A cycle C in Case 1. (b) A cycle C in Case 2. (c) A cycle C in Case 3. (d) A cycle D where it does not intersect some fragments Hi of Gk.
(a)(b)(c)(d)The ladder, denoted byLm, is a graph with VLm=ui,vi|i=1,2,…,m and ELm=uivi|i=1,2,…,m∪uiui+1,vivi+1|i=1,2,…,m−1. Then, Lm is a triangle-free 4-leg fragment with 2m vertices. It is easy to show the following statements:(i)
There is au1v1-path (respectively, umvm-path) containing all vertices of Lm(ii)
Ifm is odd, then there are a longest u1vm-path (respectively, v1um-path) containing all vertices of Lm, and a longest u1um-path (respectively, v1vm-path) missing exactly one vertex from Lm(iii)
Ifm is even, then there are a longest u1v1-path (respectively, umvm-path) containing all vertices of Lm, and a longest u1vm-path (respectively, v1um-path) missing exactly one vertex from Lm(iv)
For anyx,y,z such that x,y,z=v1,um,vm except for the case x,y,z=vm,v1,um, there is a u1x,yz-dual path containing all vertices of LmCombining a graphGk and a ladder Lm, we have the main theorem as follows.Theorem 2.
For any even numbern≥136, there is an n-vertex 3-connected cubic triangle-free plane graph with circumference n+1−3⌊n/136⌋.Proof.
For the case thatn is the multiple of 136, it is shown in Lemma 4. Assume that n is not the multiple of 136. Let k=⌊n/136⌋ and m=n−136k/2. Let G be an n-vertex graph with VG=VGk∪VLm and EG=EGk−b1a2,d1c2∪ELm∪b1u1,d1v1,uma2,vmc2 (see Figure 6). By this construction, it is easy to show that G is a 3-connected cubic triangle-free plane graph. Let C∗ be a longest cycle of Gk. Then, C∗ is a cycle defined in Case 3 of Lemma 4 which misses 3k−1 vertices from Gk. Since Gk−b1a2,d1c2 is a subgraph of G, a longest cycle of G should miss at least 3k−1 vertices, i.e., cirG≤n−3k−1.
Define pathsP: b1, u1,u2,…,um, a2, and Q: c1, v1,v2,…,vm, d2. Let C′=C∗−b1a2,d1c2∪P∪Q. Then, C′ is a cycle in G containing n+1−3k vertices. Hence, cirG=n+1−3k.Figure 6
The graphG defined in Theorem 2.


## 3. Discussion and Open Problems

It can be implied from Theorem1 and Theorem 2 that c136≤133, and cn≤n+1−3⌊n/136⌋ if n≥138. This improves most of upper bound of cn from [21, 22] except for some cases in [21]. Then, we will compare ours to that result as follows.Theorem 3 (see [21]).
For any integerk≥2 and k′≥1, there is a 3-connected cubic triangle-free plane graph with 4k+74k′+2 vertices and circumference 4k+74k′+2−min4k+8,4k′−2.Putting appropriatek and k′, this theorem gives a better upper bound of cn than ours in the following cases: cn≤n−2 if n∈90,114, cn≤n−6 if n∈150,190,230,270,310,350,390, cn≤n−10 if n∈210,266,322,378,434,490, cn≤n−14 if n∈ {270, 342, 414, 486, 558, 630}, cn≤n−16 if n∈330,390,450,510,570,630,690,750,810, cn≤n−18 if n∈418,506,594,682,770,858,946, cn≤n−20 if n∈494,570,646,722,798,874,950, cn≤n−22 if n∈598,702,806,910,1014, cn≤n−24 if n∈690,782,874,966,1058,1150, cn≤n−26 if n∈930,1050,1170, cn≤n−28 if n∈918,1026,1134,1242,1350, cn≤n−30 if n∈1054,1190,1326,1462, cn≤n−32 if n∈1178,1320,1462, cn≤n−34 if n∈1330,1482, cn≤n−36 if n∈1470,1638, cn≤n−38 if n=1638, cn≤n−40 if n=1794, and cn≤n−42 if n=1978.For an open problem, we definecPn (respectively, cTn) as the minimum of cirG, where G is a 3-connected cubic triangle-free projective plane graph (respectively, toroidal graph) with n vertices. The Petersen graph, a 10-vertex graph, is a smallest 3-connected cubic triangle-free nonhamiltonian graph which can be embedded in both projective plane and torus. This implies that cPn=cTn=n if n≤8, and cP10=cT10=9. Since a plane graph is also a projective plane graph and a toroidal graph, we have the following inequality: cPn≤cn and cTn≤cn. Then, we give the following questions.Question 1.
What is an upper bound ofcPn?Question 2.
What is an upper bound ofcTn?



---

*Source: 1593006-2021-08-14.xml*