A Note on Grünbaum's Conjecture about Longest Cycles and Paths

Abstract

Let $c(G)$ denote the circumference of a graph $G$, i.e., the number of vertices in its longest cycle. For positive integers $n$ and $k$ with $n>k$, let $\Gamma (n;k)$ be the class of graphs of order $n$ with $c(G)=n-k$ such that every induced subgraph of order $n-k$ is Hamiltonian. When $k=$, the class $\Gamma (n;1)$ coincides with the family of hypohamiltonian graphs-non-Hamiltonian graphs in which the deletion of any single vertex yields a Hamiltonian graph.Replacing Hamiltonian with traceable and $c(G)$ with $p(G)$, the order of a longest path, defines the analogous class $\Pi (n;k)$.Grünbaum (1974) conjectured that both $\Gamma (n;k)$ and $\Pi (n;k)$ are empty for all $n>k\ge 2$. In this note, we first establish upper bounds on the maximum degree of graphs in the classes $\Gamma (n;k)$ and $\Pi (n;k)$. Using these bounds, we show that $\Gamma (n;k)$ is empty when $n<k^2+2k+3$, and that $\Pi (n;k)$ is empty when $n<k^2+2k+2$. These results provide further evidence supporting Grünbaum's conjecture.