6
$\begingroup$

Definitions:
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$.

Background:
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.)

$\endgroup$

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.