Partitioning graphs into paths or cycles of prescribed lengths (Q1937351)

This paper considers the problem of partitioning a graph, \(G,\) into paths (circles) when \(\sigma_2(G),\) defined as the minimum degree sum of two non-adjacent vertices in \(V(G),\) satisfies a certain property. Readers are referred to [\textit{H. Enomoto}, Discrete Math. 233, No. 1--3, 93--101 (2001; Zbl 0985.05036)] for a survey of this problem and the associated results. Besides being theoretically interesting, such results also play a crucial role in designing interconnection networks where existence of pairwise disjoint paths will make a specific network structure much more appealing. Thus, this problem also has important applications. Based on Ore's classical result [\textit{Ø. Ore}, J. Math. Pures Appl., IX. Sér. 42, 21--27 (1963; Zbl 0106.37103)] on a sufficient condition of a graph being Hamiltonian, one can derive the following result, which starts this line of research: Let \(t\) (\(\geq 2\)) be a positive integer, and let \(G\) be a graph, \(|V(G)|=n\), if \(\sigma_2(G) \geq n,\) then for any \(t\) vertices \(x_1, \dots, x_t\) in \(V(G)\), there exist \(t\) pairwise disjoint paths \(P_1, \dots, P_t\) such that \(V(G)=\bigcup_{i=1}^t V(P_i)\) and, for all \(i \in [1, n]\), \(x_i\) is an end vertex of \(P_i\). The above result is later augmented with a sharp \(\sigma_2(G)\) bound that guarantees a partition of \(G\) into disjoint paths with one specified vertex and a given order [\textit{Y. Chen, F. Tian} and \textit{B. Wei}, Graphs Comb. 17, No. 1, 61--71 (2001; Zbl 0987.05080)]. This current paper continues with this line of research by partitioning a graph into disjoint paths with a given order, where both vertices of these paths are specified. The ultimate goal of this line seems to be the following, as captured with Conjecture~2: Let \(t\) (\(\geq 2\)) be a positive integer, \(a_1, \dots, a_t\) be positive integers, and let \(G\) be a graph, \(|V(G)|=n=\sum_{i=1}^t a_i\). If \(\sigma_2(G) \geq n+2t-1\), then for any \(2t\) vertices \((x_1, y_1), \dots, (x_t, y_t)\), in \(V\), there exist \(t\) pairwise disjoint paths \(P_1, \dots, P_t\) such that \(V = \bigcup_{i=1}^t V(P_i)\) and, for all \(i \in [1, n],\) \((x_i, y_i)\) are end vertices of \(P_i\) and \(|P_i|=a_i\). The main result (Theorem 4) as presented and proved in this paper is the following: Let \(t\) (\(\geq 2\)) be a positive integer, for any set of \(t\) positive real numbers \(\gamma_1, \dots, \gamma_t\), \(\sum_{i=1}^t \gamma_i=1\), and for every \(\epsilon \in \left(0,\min_i \{\frac{1}{{18}^2t^2}, \frac{\gamma_i}{2} \}\right]\), there exists an integer \(n_0\) such that for every \((2n+1)\)-connected graph \(G\), \(|V(G)|=n \geq n_0\) with \(\sigma_2(G) \geq n+2t-2\) and for any \(2t\) vertices \((x_1, y_1), \dots, (x_t, y_t) \) in \(V(G)\), there exist \(t\) pairwise disjoint paths \(P_1, \dots, P_t\) such that \(V=\bigcup_{i=1}^t V(P_i)\) and, for all \(i \in [1, n]\), \((x_i, y_i)\) are end vertices of \(P_i\) and \((\gamma_i-\epsilon)n \leq |P_i| \leq (\gamma_i+\epsilon)n\). A similar pair of results are also given on partitioning a graph into disjoint cycles, where the \(\sigma_2(G)\) condition is slightly strengthened to \(\sigma_2(G)\geq n+2t-2\). The proof of the above main result is a lengthy and constructive process built on a series of technical claims and lemmas, which constitute the bulk of this paper. It is clear that there are still a lot to do in proving the validity of the aforementioned conjecture.