On 2-power unicyclic cubic graphs

Shariefuddin Pirzada, Mushtaq Shah, Edy Tri Baskoro

Abstract


In a graph, a cycle whose length is a power of two (that is, 2k) 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árfás conjecture.


Keywords


cycle, cubic graph, Erdos-Gyarfas conjecture, distance

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2022.10.1.24

References

J. Bensmail, On q-power cycles in cubic graphs. Discussions Mathematics Graph Theory 37 (2017), 211–220.

D. Dale and S.E. Shauger, A result on the Erdos-Gyárfás conjecture in planar graphs, Proc. 32nd Southeastern Int. Conf. Combinatorics, Graph Theory and Computing, 56 (2001), 129–13.

C. Dalfo, M.A. Fiol, and M. Mitjana, On middle cube graphs, Electron. J. Graph Theory Appl. 3 (2) (2015), 133–145.

P. Erdos, Some old and new problems in various branches of combinatorics, Discrete Math. 165 (1997), 227–231.

D. Frank, On the k-diameter of k-regular k-connected graphs, Discrete Math. 133 (1994), 291–296.

C. Heckman and R. Krakovski, Erdos-Gyárfás conjecture for cubic planar graphs, Electronic J. Comb. 2 (2013) p7.

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.

K. Markstrum, Extremal graphs for some problems on cycles in Graphs, Congr. Numerantium 171 (2004) 179–192.

S. Pirzada, An Introduction to Graph Theory, Universities Press, Orient BlackSwan, Hyderabad (2012).

S.E. Shauger, Results on the Erdos-Gyárfás conjecture in K1, m-free graphs, Proc. 29th South-eastern Int. Conf. Combinatorics, Graph Theory and Computing, (1998) 61-65.

B. Sudakov and J. Verstraete, Cycle lengths in sparse graph, Combinatorica 28 (3) (2008) 357- 372.

J. Verstraete, Unavoidable cycle lengths in graphs, J. Graph Theory 49 (2) (2005) 151-167.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats