Chorded Pancyclicity in k -Partite Graphs

Research paper by Daniela Ferrero, Linda Lesniak

Indexed on: 26 Aug '18Published on: 23 Aug '18Published in: Graphs and Combinatorics


Abstract We prove that for any integers \(p\ge k\ge 3\) and any k-tuple of positive integers \((n_1,\ldots ,n_k)\) such that \(p=\sum _{i=1}^k{n_i}\) and \(n_1\ge n_2\ge \cdots \ge n_k\) , the condition \(n_1\le {p\over 2}\) is necessary and sufficient for every subgraph of the complete k-partite graph \(K(n_1,\ldots ,n_k)\) with at least $$\begin{aligned} {{4 -2p+2n_1+\sum _{i=1}^{k} n_i(p-n_i)}\over 2} \end{aligned}$$ edges to be chorded pancyclic. Removing all but one edge incident with any vertex of minimum degree in \(K(n_1,\ldots ,n_k)\) shows that this result is best possible. Our result implies that for any integers, \(k\ge 3\) and \(n\ge 1\) , a balanced k-partite graph of order kn with has at least \({{(k^2-k)n^2-2n(k-1)+4}\over 2}\) edges is chorded pancyclic. In the case \(k=3\) , this result strengthens a previous one by Adamus, who in 2009 showed that a balanced tripartite graph of order 3n, \(n \ge 2\) , with at least \(3n^2 - 2n + 2\) edges is pancyclic.