Article

An Asymptotic Version of a Conjecture by Enomoto and Ota

Journal of Graph Theory
(2010)
Abstract

In 2000, Enomoto and Ota [J Graph Theory 34 (2000), 163–169] stated the following conjecture. Let

*G*be a graph of order*n*, and let*n*1,*n*2, …,*n*k be positive integers with . If σ2(*G*)≥*n*+*k*−1, then for any*k*distinct vertices*x*1,*x*2, …,*x*k in*G*, there exist vertex disjoint paths*P*1,*P*2, …,*P*k such that |*P*i|=*n*i and*x*i is an endpoint of*P*i for every*i*, 1≤*i*≤*k*. We prove an asymptotic version of this conjecture in the following sense. For every*k*positive real numbers γ1, …, γk with , and for every ε>0, there exists*n*0 such that for every graph*G*of order*n*≥*n*0 with σ2(*G*)≥*n*+*k*−1, and for every choice of*k*vertices*x*1, …,*x*k∈*V*(*G*), there exist vertex disjoint paths*P*1, …,*P*k in*G*such that , the vertex*x*i is an endpoint of the path*P*i, and (γi−ε)*n*<|*P*i|<(γi + ε)*n*for every*i*, 1≤*i*≤*k*.Keywords

- Paths,
- Graph decomposition,
- Degree sum

Disciplines

Publication Date

May, 2010
DOI

10.1002/jgt.20437
Citation Information

Colton Magnant and Daniel M. Martin. "An Asymptotic Version of a Conjecture by Enomoto and Ota" *Journal of Graph Theory*Vol. 64 Iss. 1 (2010) p. 37 - 51 ISSN: 1097-0118

Available at: http://works.bepress.com/colton_magnant/8/