Lower bounds of length of longest cycles in graphs involving neighborhood unions (Q1357727)

The author proves lower bounds for the circumference of 3- or 4-connected graphs in terms of their minimum neighbourhood union. Let \(c(G)\) be the circumference, i.e. the length of the longest cycle in \(G\), and let \(\text{NC} (G)\) be the minimum cardinality of a neighbourhood union \(N(x) \cup N(y)\), the minimum taken over all pairs of nonadjacent vertices \(x,y\). The author shows that if \(G\) is 3-connected, then \(c(G)\geq \min (n,{3 \over 2} (\text{NC} (G)+1))\) and if \(G\) is 4-connected, then \(c(G) \geq\min (n,2 \text{NC} (G))\), thereby proving a conjecture of Faudree, Gould, Jacobson and Schelp. Both bounds are reached for infinitely many \(G\). The example of \(K_{\text{NC}, n-\text{NC}}\) shows that the second is sharp even for all possible pairs \(n,\text{NC}\).