Let $G$ be a graph on $n$ vertices. $G$ is Hamiltonian provided $G$ has a cycle of length $n$. $G$ is pancyclic provided $G$ has a cycle of length $\ell$ for every $3 \leq \ell \leq n$.

Dirac [1952] showed that if $G$ has $n \geq 3$ vertices and every vertex has degree at least $\frac{n}{2}$, then $G$ is Hamiltonian. Bondy [1971] showed this condition implies that either $G$ is the complete bipartite graph $K_{\frac{n}{2},\frac{n}{2}}$ or $G$ is pancyclic. Bondy [1973] then proposed the following metaconjecture (which I quote from Kevash and Sudakov 2010):

Metaconjecture. Almost any non-trivial condition on a graph which implies that the graph is Hamiltonian also implies that the graph is pancyclic. (There may be a simple family of exceptional graphs.)

Another instance of this metaconjecture is the following corollary of a theorem of Clark [1981].

Let $G$ be a connected, locally connected, claw-free graph on at least $3$ vertices. Then $G$ is pancyclic.

Given property $\mathcal{P}$ (such as "connected"), a graph is locally $\mathcal{P}$ provided the neighborhood of every vertex is $\mathcal{P}$. A graph is claw-free provided it has no induced copies of $K_{1,3}$. Being claw-free is equivalent to being locally $\overline{K_3}$-free.

It seems to me that such local properties might eliminate bothersome exceptional cases. Might we be able to prove a localized version of Bondy's metaconjecture such as the following?

Tentative Subconjecture. Let $\mathcal{P}$ be a graph property such that every connected graph on at least $3$ vertices that is locally $\mathcal{P}$ is Hamiltonian. Then every connected graph on at least $3$ vertices that is locally $\mathcal{P}$ is pancyclic.

A monotonicity assumption on the property--for example, if $A$ satisfies $\mathcal{P}$ and $A$ is a subgraph of $B$ and $|A|=|B|$ then $B$ satisfies $\mathcal{P}$--might also be useful.

(This question is inspired by Ortrud Oellermann's presentation at the 2016 Prairie Discrete Math Workshop.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.