A note on pancyclicity of $k$-partite graphs

Research paper by Daniela Ferrero, Linda Lesniak

Indexed on: 23 Jan '18Published on: 23 Jan '18Published in: arXiv - Mathematics - Combinatorics


In 2009, Adamus showed that if $G$ is a balanced tripartite graph of order $3n$, $n \geq 2$, with at least $3n^2 - 2n + 2$ edges, then $G$ is hamiltonian and, in fact, $G$ is pancyclic. Removing all but one edge incident with any vertex of the complete, balanced tripartite graph $K(n,n,n)$ shows that this result is best possible. Here we extend the result to balanced $k$-partite graphs of order $kn$. We prove that for all integers $k\geq 3$ and $n\geq 1$, every balanced $k$-partite graph with $kn$ vertices and at least ${{(k^2-k)n^2-2n(k-1)+4}\over 2}$ edges is pancyclic. We also prove a similar result for $k$-partite graphs that are not balanced.