Some panconnected and pancyclic properties of graphs with a local Ore-type condition (Q1923776): Difference between revisions

Call \(\mathcal L\) the class of all finite undirected graphs that are not complete bipartite, have at least 5 vertices and satisfy \(d(u)+d(v)\geq|N(u)\cup N(v)\cup N(w)|\) for all paths \(uwv\) with \(u\) and \(v\) non-adjacent. It is proved that the elements of \(\mathcal L\) have a large amount of paths and cycles, as precised by the following statements, satisfied by all elements \(G\in{\mathcal L}\). (1) For each pair \(u\) and \(v\) of vertices with \(d(u,v)\geq 3\) and for each \(\ell\) with \(d(u,v)\leq\ell\leq|V(G)|\), there is a path of length \(\ell\) between \(u\) and \(v\). (2) For each edge \(e\) not in a triangle and for each \(\ell\) with \(4\leq\ell\leq|V(G)|\), there is a cycle of length \(\ell\) not containing \(e\). (3) For each vertex \(v\) and for each \(\ell\) with \(4\leq\ell\leq|V(G)|\), there is a cycle of length \(\ell\) containing \(v\). As a consequence of further results obtained in this context, it is proved that \(G\) is not only Hamiltonian, but pancyclic.