On the panconnectivity of graphs with large degrees and neighborhood unions
It is shown that if \(G\) is a \(3\)-connected graph of order \(n\) such that for any triple of independent vertices \(\{u,v,w\}\), the \(\min \{| N(u) \cup N(v)|+ d(w), | N(u) \cup N(w)|+ d(v), | N(v) \cup N(w)|+ d(u) \} \geq n+ 1\), then \(G\) is \([7,n]\)-panconnected. There is a corresponding result for \(2\)-connected graphs if certain pairs of cutvertices are avoided. Let \(\text{NC}(G)\) be the minimum number of vertices in the union of the neighborhood of any pair of nonadjacent vertices of the graph \(G\). A corollary of this is that if \(\text{NC}(G)+ \delta(G) \geq n+ 1\), then \(G\) is vertex pancyclic. This confirms a conjecture of \textit{R. J. Faudree} et al. in [Ars Comb. 31, 139-148 (1991; Zbl 0739.05056)].
scientific article; zbMATH DE number 1211726