Graph partition into paths containing specified vertices
Let \(G\) be a graph of order \(n\), and let \(\sigma_2(G)\) be the minimum degree sum of a pair of nonadjacent vertices. Recently, Enomoto and Ota conjectured that, if a partition \(n=\sum_{i=1}^k a_i\) is given and \(\sigma_2(G)\geq n+k-1\), then for any \(k\) distinct vertices \(v_1,v_2,\ldots,v_k\), the graph \(G\) can be decomposed into vertex-disjoint paths \(P_1,P_2,\ldots,P_k\) such that \(|V(P_i)|=a_i\) and \(v_i\) is an endvertex of \(P_i\) for \(i=1,2,\ldots,k\). Enomoto and Ota verified their conjecture for \(k\leq 3\) or \(a_i\leq 5\) for all \(i\). In this paper, the author proves this conjecture under the stronger assumption that \(\sigma_2(G)\geq\sum_{i=1}^k\max(\lfloor 4a_i/3\rfloor,a_i+1)-1\).
scientific article; zbMATH DE number 1746267