On 2-power unicyclic cubic graphs

S. Pirzada^∗a , Mushtaq A. Shah^b , Edy Tri Baskoro^c

pirzadasd@kashmiruniversity.ac.in, shahmushtaq81@gmail.com, ebaskoro@itb.ac.id

In a graph, a cycle whose length is a power of two (that is, 2 k ) is called a 2-power cycle. In this paper, we show that the existence of an infinite family of cubic graphs which contain only one cycle whose length is a power of 2. Such graphs are called as 2-power unicyclic cubic graphs. Further we observe that the only 2-power cycle in a cubic graph cannot be removed implying that there does not exist a counter example for Erdos-Gy ˝ arf ´ as conjecture. ´

Keywords: cycle, cubic graph, Erdos-Gy ˝ arf ´ as conjecture, distance ´

Mathematics Subject Classification: 05C38

DOI: 10.5614/ejgta.2022.10.1.24

1. Introduction

In a graph G, a 2-power cycle is a cycle whose length is a power of 2. A graph which contains a unique 2-power cycle is called a 2-power unicyclic graph. In 1995, Erdos and Gy ˝ arf ´ as [4] put ´ forward a conjecture which states that every graph with minimum degree 3 contains a simple cycle whose length is a power of two. If the conjecture is false, a counter example would take the form of a graph with minimum degree three having no cycles whose length is a power of two. It is known through computer searches of Gordon Royle and Klas Markstrom that any counterexample must have at least 17 vertices, and any cubic counter example must have at least 30 vertices. Markstrom's searches found four graphs on 24 vertices in which the only power-of-two cycles have 16 vertices, one of these four graphs is planar. However, the Erdos-Gy ˝ arf ´ as conjecture is now known to be true ´

Received: 4 March 2021, Revised: 10 April 2022, Accepted: 16 April 2022.

^aDepartment of Mathematics, University of Kashmir, Srinagar, Kashmir, India

^bDepartment of Mathematics, AAAM Degree College, Bemina, Srinagar, India

^cCombinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Indonesia

^∗Corresponding author

for the special case of 3-connected cubic planar graphs, see Heckman and Krakovski [6]. Weaker results relating the degree of a graph to unavoidable sets of cycle lengths are known. Verstraete [12] showed that there is a set S of lengths, with \(|S| = O(n^{0.99})\), such that every graph with average degree ten or more contains a cycle with its length in S. Sudakov and Verstraete [11] proved that every graph whose average degree is exponential in the iterated logarithm of n necessarily contains a cycle whose length is a power of two. Daniel and Shauger [2] proved the conjecture to be true for planar claw-free graphs and Shauger [10] showed the conjecture to be true for graphs that avoid large induced stars and satisfy additional constraints on their degrees. In 2004, Klas Markstrom [8] provided extremal graphs for some problems on cycles in graphs.

A graph is planar if it can be embedded in the plane without crossing edges. A plane graph is an embedded planar graph. A graph G is 3-connected if it becomes disconnected by removing at least 3 vertices. A graph G is cubic if every vertex of G is of degree three. More on graphs and cycles can be seen in [3, 7, 9].By computer searches, Markstrom [6] verified Erdős-Gyárfás conjecture for cubic graphs of order at most 29, and found that the smallest cubic planar graph with no 4-or 8-cycles has 24 vertices (see Figure 1). Note that this graph contains a 16-cycle. Shauger [8] proved the conjecture for \(K_{1,m}\) free graphs of minimum degree at least m+1 or maximum degree at least 2m-1. Every 3-connected cubic planar graph contains a \(2^m\) cycle, for some \(2 \le m \le 7\), see [6].

Figure 1. cubic graph with 24 vertices with no 4- or 8-cycle.

Markstrom's 24-vertex cubic planar graph with no 4 or 8 cycles, found in a computer search for counter example to the Erdős-Gyárfás conjecture, has cycles with 16 vertices. A recent study by Bensmail [1] showed that their exist arbitrarily large cubic graphs with no q-power cycle. Frank [5] showed that every k-regular k-connected graph on n vertices has k-diameter at most \(\frac{n}{2}\) and this upper bound cannot be improved when n=4k-6+I(2k-4). In particular, the maximal 3-diameter of 3-regular graphs with 2n vertices is equal to n, that is, the maximal 3-diameter of 3-regular graphs with n vertices is equal to n.

In a graph, the distance between the two vertices is the number of edges in a shortest path (also called a graph geodesic) connecting them. This is also known as the geodesic distance. Notice that there may be more than one shortest path between two vertices. If there is no path connecting the two vertices, that is, if they belong to different connected components, then conventionally the distance is defined as infinite.

2. On two power unicyclic cubic graphs

In a graph G, if the distance between the vertices u and v is d(u, v) = r, the number of vertices between u and v is r + 1. If G is a cubic graph of order n and e is any edge of G, then G − e is the graph in which n − 2 vertices are of degree 3 and 2 vertices are of degree 2, such a graph is called an (n − 2)-cubic graph.

Figure 2. Cubic graph with eight vertices.

Figure 3. 6-cubic graph, that is, graph with eight vertices with six vertices of degree 3 and two vertices of degree 2.

The graph G, shown in Figure 2, has eight vertices and contains cycles of length 4, 5, 6, 7 and 8. Now remove the edge e = uv from G, we get the graph K = G − e, as shown in Figure 3. Clearly K is (n − 2)−cubic and has no cycles of lengths 2 2 , 2 3 . Further the distance between the vertices u and v in K is dK(u, v) = 3 < 4.

We will show that the above example leads to the existence of a family of 2-power unicyclic cubic graphs, that is, a family of cubic graphs which contain only the cycle of length 2 k (2 ^k < n) but does not contain any cycle of length 2 t , t ̸= k. We show the existence of this graph G by construction, the graph G constructed will have even number of vertices, say n = 2s, and further in G there is always a bridge which partitions V (G) into two parts with each part having s vertices. So if G contains a cycle of length 2 k , then 2 ^k < s, since the presence of bridge does not allow the cycle to have edges from both the parts, that is, contains edges from one of the two parts.

Theorem 2.1. There exists a family of 2-power unicyclic cubic graphs, that is a family of cubic graphs with order say n = 2s, which contain a cycle of length \(2^k\) (\(2^k < s\)) but does not contain any cycle of length \(2^t\), \(t \neq k\).

Proof. We show the existence of such a family by construction. We start with the construction of the smallest such graph.

Consider the graph G of order 8 as shown in Figure 2. We remove the edge e=uv to get the graph K=G-e as shown in Figure 3. We note that \(d_K(u)=2\) and \(d_K(v)=2\) so that K is (6)-cubic. Further \(d_H(u,v)=3<4\). Take 5 copies of K and name them as \(H_1,H_2,J_1,J_2\) and H. Also we represent the vertices of degree 2 by \(u_1,v_1\in H_1;\ u_2,v_2\in H_2;\ x_1,y_1\in J_1;\ x_2,y_2\in J_2\) and \(u,v\in H\). Further, let \(P_1=H_1\cup H_2\) and \(Q_1=J_1\cup J_2\).

Now, let \(X_1\) be the graph consisting of \(P_1, Q_1, H\), \(K_3\) (vertices labeled as \(w_1, w_2, w_3\)) and \(K_{1,3} + x\) (vertices labeled as \(z_1, z_2, z_3, z_4\) with \(z_1\) as the pendant vertex) together with the edges \(v_1u_2, y_1x_2, v_2w_1, y_2w_2, w_3v, uz_1, u_1z_3, x_1z_4\). Clearly degree of each vertex of \(X_1\) is three except the vertex \(z_1\) whose degree is two.

We now take two copies of \(X_1\), one named as \(X_1\) and another as \(X_1'\). Label the vertices of \(X_1'\) as \(u_1', v_1'\) and so on. Consider the graph \(G_1 = X_1 \cup X_1' \cup \{z_1 z_1'\}\). Clearly the graph \(G_1\) is cubic.

Figure 4. Cubic graph \(G_1\) with 94 vertices, having no cycles of length 4, 8, 16 but has a cycle of length 32.

We observe that the edge \(z_1z_1'\) is a bridge in \(G_1\) (joining \(X_1\) and \(X_1'\)). Also the number of vertices in each of \(X_1\) and \(X_1'\) is 47. So the maximum length of the cycle in \(G_1\) has to be less or equal to 47 and thus \(G_1\) can have only \(2^2, 2^3, 2^4, 2^5\) cycles of the form \(2^k\). But as we see that \(G_1\) does not contain the cycles of the lengths \(2^2, 2^3, 2^4\). Evidently \(G_1\) contains the cycle of length \(2^5\). Note that \(G_1\) cannot have a cycle of length \(2^6 = 64\), because of the presence of bridge \(z_1z_1'\)

between \(X_1\) and \(X'_1\). Hence we have constructed a cubic graph \(G_1\) of order 84 in which there are no cycles of lengths \(2^2\), \(2^3\), \(2^4\) but it contains a cycle of length of \(2^5\). See Figure 4.

The above construction can be extended to obtain a family of cubic graphs in the following way. Let \(P_i\) contain \(\sum_{j=1}^i 2^j\) copies of K and name these copies as \(H_1, H_2, H_3, \ldots\) Let \(P_i = H_1 \cup H_2 \cup H_3 \cup \ldots\) Similarly let \(Q_i\) contain \(\sum_{j=1}^i 2^j\) copies of K and name these copies as \(J_1, J_2, J_3, \ldots\) Let \(Q_i = J_1 \cup J_2 \cup J_3 \cup \ldots\) Label the vertices of degree 2 in \(H_1, H_2, H_3, \ldots\), \(J_1, J_2, J_3, \ldots\) respectively by \(u_1, v_1 \in H_1\); \(u_2, v_2 \in H_2\); \(u_3, v_3 \in H_3\); \(\ldots\); \(x_1, y_1 \in J_1\); \(x_2, y_2 \in J_2\); \(x_3, y_3 \in J_3, \ldots\)

Let \(X_i\) be the graph containing \(P_i, Q_i, H\) (a copy of K), \(K_3\) (vertices labeled as \(w_1, w_2, w_3\)) and \(K_{1,3} + x\) (vertices labeled as \(z_1, z_2, z_3, z_4\) with \(z_1\) as the pendant vertex) together with the edges \(v_1u_2, v_2u_3, \ldots\); \(y_1x_2, y_2x_3, \ldots\); \(w_3v, uz_1, u_1z_3, x_1z_4\); the edge between the vertex \(w_1\) and the second vertex of the last copy \(K \in P_i\); the edge between \(w_2\) and the second vertex of the last copy \(K \in Q_i\). Clearly degree of each vertex of \(X_i\) is three except the vertex \(z_1\) whose degree is two. Now, take two copies of \(X_i\), represented as \(X_i\) and \(X_i'\).

Consider the graph \(G_i = X_i \cup X_i' \cup \{z_1 z_1'\}\), which is cubic. We observe that the edge \(z_1 z_1'\) is a bridge in \(G_i\) (joining \(X_i\) and \(X_i'\)). Also the number of vertices in each of \(X_i\) and \(X_i'\) is \(|X_i| = |P_i| + |Q_i| + |H| + |K_3| + |K_{1,3} + x| = 2|P_i| + 8 + 3 + 4 = 2(8\sum_{j=1}^i 2^j) + 15\), since each copy of K contains eight vertices. Thus the length of the largest cycle has to be less or equal to \(2(8\sum_{j=1}^i 2^i) + 15 = 2^4(2 + 2^2 + 2^3 + \dots + 2^{i-1} + 2^i) + 15\). Further, we note that \(|X_i| = |X_{i-1}| + 2^{i+1}\). If \(|G_i|\) is the order of \(G_i\), it can be easily seen that \(|G_i| = |G_{i-1}| + 2^5\).

Evidently, \(G_i\) does not contain the cycles of lengths \(2^2, 2^3, 2^4, \dots, 2^{i+3}\) but contains the cycle of length \(2^{i+4}\). Also \(G_i\) does not contain the cycles of length \(2^t, t \ge i+5\), since the length of the largest cycle is less or equal to \(2^4(2+2^2+2^3+\cdots+2^{i-1}+2^i)+15\). Hence \(G_i\) contains only one cycle whose length is a power of 2.

For instance, \(G_2\) is a cubic graph of order 222 having no cycles of lengths \(2^2, 2^3, 2^4, 2^5\) but it contains a cycle of length \(2^6\), see Figure 5. This is because the graph has a bridge and each part has 111 vertices. The minimum length of the cycle is 33 and total vertices in each part is 111. Thus, the only cycle whose length is of the form \(2^k\) with \(33 \le 2^k \le 111\) is 64.

Similarly, \(G_3\) is a cubic graph of order 478 having no cycles of lengths \(2^2, 2^3, 2^4, 2^5, 2^6\) but it contains a cycle of length \(2^7\). This is illustrated in Figure 6. This graph has a bridge, so each part has 239 vertices and minimum length of a cycle is 65 and total vertices in each part is 239. Therefore, the only cycle of the form \(2^k\) with \(65 \le 2^k \le 239\) is 128.

From the above discussion and examples, we get a recurrence relation of these cubic graphs as follows.

Let us assume that there exists a cubic graph G which contains a cycle of length \(2^k\) only but does not contain cycles of length \(2^t\), \(t \neq k\). In particular, G will have no cycles of length \(2^t\), \(2 \leq t \leq k-1\). Thus the number of vertices in this graph is at least \(2^k\), that is, \(n \geq 2^k\), where n is the total number of vertices in the graph. Since it has no cycle of length \(2^{k-1}\), this implies that an edge was removed in the graph between vertices u and v (say) which has removed all the cycles of length \(2^t\), \(2 \leq t \leq k-1\). Thus \(d(u,v) = 2^{k-1}-1\). As \(2^{k-1} < 2^k\), implies that \(2(2^{k-1}) = 2^k\), or \(2(2^{k-1}-1) < 2^k\), or \(2^{k-1}-1 < \frac{2^k}{2}\) or \(2^{k-1}-1 < \frac{n}{2}\), where \(n \geq 2^k\). Thus, \(d(u,v) < \frac{n}{2}\), which negates the above observation that each cubic graph with degree greater or equal to 3 has one cycle

Figure 5. Cubic graph G² with 222 vertices, having no cycles of length 4,8,16,32 but has a cycle of length 64.

Table 1. Recurrence relation for the cubic graphs

of length 2 k . Accordingly, there is no cubic graph in which we can develop a counter case with no cycle of power 2 k . This way we conclude that every graph with minimum degree 3 contains a cycle whose length is a power of two.

Figure 6. Cubic graph G³ with 478 vertices, having no cycles of length 4, 8, 16, 32, 64 but has a cycle of length 128.

3. Conclusion

The Erdos-Gy ˝ arf ´ as conjecture is one of the important problems in graph theory. The problem ´ has been partially proved to be true. Daniel and Shauger proved the conjecture to be true for planar claw-free graphs and Shauger showed the conjecture to be true for graphs that avoid large induced stars and satisfy additional constraints on their degrees.

The main aim of this paper is to show that counter example for the conjecture is not possible. For this, we first prove the existence of an infinite family of cubic graphs which contain only one cycle whose length is a power of 2. We show the existence of a family of cubic graphs in which all the cycles of the form 2 t , where 2 ≤ t ≤ k − 1, can be removed and does contain only a cycle of order 2 k , 2 ^k < n. Such graphs are called as 2-power unicyclic cubic graphs. Further, we observe that the only 2-power cycle in a cubic graph cannot be removed implying that there does not exist a counter example for Erdos-Gy ˝ arf ´ as conjecture. ´

Acknowledgement

The authors are grateful to the anonymous referee for his useful comments. The research of S. Pirzada is supported by SERB-DST under the research project number CRG/ 2020/000109.

References

• [1] J. Bensmail, On q-power cycles in cubic graphs. Discussions Mathematics Graph Theory 37 (2017), 211–220.
• [2] D. Dale and S.E. Shauger, A result on the Erdos-Gy ˝ arf ´ as conjecture in planar graphs, ´ Proc. 32nd Southeastern Int. Conf. Combinatorics, Graph Theory and Computing, 56 (2001), 129– 13.
• [3] C. Dalfo, M.A. Fiol, and M. Mitjana, On middle cube graphs, Electron. J. Graph Theory Appl. 3 (2) (2015), 133–145.
• [4] P. Erdos, Some old and new problems in various branches of combinatorics, ˝ Discrete Math. 165 (1997), 227–231.
• [5] D. Frank, On the k-diameter of k-regular k-connected graphs, Discrete Math. 133 (1994), 291–296.
• [6] C. Heckman and R. Krakovski, Erdos-Gy ˝ arf ´ as conjecture for cubic planar graphs, ´ Electronic J. Comb. 2 (2013) p7.
• [7] B. Li, L. Xiong, and J. Yin, Least degree vertices in longest cycles of graphs II, Electron. J. Graph Theory Appl. 7 (2) (2020) 277–299.
• [8] K. Markstrum, Extremal graphs for some problems on cycles in Graphs, Congr. Numerantium 171 (2004) 179–192.
• [9] S. Pirzada, An Introduction to Graph Theory, Universities Press, Orient BlackSwan, Hyderabad (2012).
• [10] S.E. Shauger, Results on the Erdos-Gy ˝ arf ´ as conjecture in ´ K1,m-free graphs, Proc. 29th Southeastern Int. Conf. Combinatorics, Graph Theory and Computing, (1998) 61-65.
• [11] B. Sudakov and J. Verstraete, Cycle lengths in sparse graph, Combinatorica 28 (3) (2008) 357- 372.
• [12] J. Verstraete, Unavoidable cycle lengths in graphs, J. Graph Theory 49 (2) (2005) 151-167.