# Chorded Pancyclicity in k -Partite Graphs

Research paper by **Daniela Ferrero, Linda Lesniak**

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

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

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.