An asymptotic version of a conjecture by Enomoto and Ota

✍ Scribed by Colton Magnant; Daniel M. Martin

• Publisher: John Wiley and Sons
• Year: 2009
• Tongue: English
• Weight: 172 KB
• Volume: 64
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20437

✦ Synopsis

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. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 37–51, 2010