2018/01/24 by Ferrero, Daniela, Lesniak, Linda
#05C45 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1801.07854
We prove that for any integers p≥ k≥ 3 and any k-tuple of positive integers (n1,… ,nk) such that p=∑ i=1kni and n1≥ n2≥ … ≥ nk, the condition n1≤ p\over 2 is necessary and sufficient for every subgraph of the complete k-partite graph K(n1,… ,nk) with at least 4 -2p+2n1+∑ i=1k ni(p-ni)\over 2 edges to be chorded pancyclic. Removing all but one edge incident with any vertex of minimum degree in K(n1,… ,nk) shows that this result is best possible. Our result implies that for any integers, k≥ 3 and n≥ 1, a balanced k-partite graph of order kn with has at least (k2-k)n2-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 ≥ 2, with at least 3n2 - 2n + 2 edges is pancyclic.