A survey and strengthening of Erdős-Gyarfas conjecture (Q1677333)

Erdős-Gyarfas conjecture states that every graph with minimum degree 3 contains a simple cycle whose length is a power of 2. In this paper, the authors prove that if a graph \(G\) of order \(n\) having \(n-2\) vertices of degree 3 and two vertices of degree 2 does not contain a cycle of length \(2^n\) and the distance between the vertices of degree 2 is \(n/2+1\) and this number is odd, then there exists a cubic graph which does not contain a cycle of length \(2^n\).