pith. sign in

arxiv: 1801.07854 · v3 · pith:WRF7NAX6new · submitted 2018-01-24 · 🧮 math.CO

Chorded pancyclicity in k-partite graphs

classification 🧮 math.CO
keywords ldotschordededgesgraphintegersleastpancyclicpartite
0
0 comments X
read the original abstract

We prove that for any integers $p\geq k\geq 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\geq n_2\geq \ldots \geq n_k$, the condition $n_1\leq {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 \[{{4 -2p+2n_1+\sum _{i=1}^{k} n_i(p-n_i)}\over 2}\] 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\geq 3$ and $n\geq 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 \geq 2$, with at least $3n^2 - 2n + 2$ edges is pancyclic.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.