Enomoto and Ota’s Conjecture Holds for Large Graphs

Abstract

In 2000, Enomoto and Ota conjectured that if a graph G satisfies $\sigma _{2}(G) \ge |G| + k - 1$, then for any set of k vertices $v_{1}, \ldots , v_{k}$ and for any positive integers $n_{1}, \ldots , n_{k}$ with $\sum n_{i} = |G|$, there exists a partition of V(G) into k paths $P_{1}, \ldots , P_{k}$ such that $v_{i}$ is an end of $P_{i}$ and $|P_{i}| = n_{i}$ for all i. We prove this conjecture when |G| is large. Our proof uses the Regularity Lemma along with several extremal lemmas, concluding with an absorbing argument to retrieve misbehaving vertices.