Note on Enomoto and Ota’s Conjecture for Short Paths in Large Graphs

Martin Hall; Colton Magnant; Hua Wang

doi:10.1007/s00373-013-1351-7

Note on Enomoto and Ota’s Conjecture for Short Paths in Large Graphs

Martin Hall
, Colton Magnant
, Hua Wang

Mathematical Sciences

Georgia Southern University

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

With sufficient minimum degree sum, Enomoto and Ota conjectured that for any selected set of vertices, there exists a spanning collection of disjoint paths, each starting at one of the selected vertices and each having a prescribed length. Using the Regularity Lemma, we prove that this claim holds without the spanning assumption if the vertex set of the host graph is sufficiently large.

Original language	American English
Journal	Graphs and Combinatorics
Volume	30
DOIs	https://doi.org/10.1007/s00373-013-1351-7
State	Published - Nov 1 2014

Disciplines

Education
Mathematics

Keywords

Degree sum
Disjoint paths
Regularity lemma

Access to Document

10.1007/s00373-013-1351-7License: Unspecified

https://doi.org/10.1007/s00373-013-1351-7

Cite this

@article{e2fe405e9baa46d9b6d73df09a23331c,

title = "Note on Enomoto and Ota{\textquoteright}s Conjecture for Short Paths in Large Graphs",

abstract = "With sufficient minimum degree sum, Enomoto and Ota conjectured that for any selected set of vertices, there exists a spanning collection of disjoint paths, each starting at one of the selected vertices and each having a prescribed length. Using the Regularity Lemma, we prove that this claim holds without the spanning assumption if the vertex set of the host graph is sufficiently large.",

keywords = "Degree sum, Disjoint paths, Regularity lemma",

author = "Martin Hall and Colton Magnant and Hua Wang",

note = "Publisher Copyright: {\textcopyright} 2013, Springer Japan.",

year = "2014",

month = nov,

day = "1",

doi = "10.1007/s00373-013-1351-7",

language = "American English",

volume = "30",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

}

TY - JOUR

T1 - Note on Enomoto and Ota’s Conjecture for Short Paths in Large Graphs

AU - Hall, Martin

AU - Magnant, Colton

AU - Wang, Hua

PY - 2014/11/1

Y1 - 2014/11/1

N2 - With sufficient minimum degree sum, Enomoto and Ota conjectured that for any selected set of vertices, there exists a spanning collection of disjoint paths, each starting at one of the selected vertices and each having a prescribed length. Using the Regularity Lemma, we prove that this claim holds without the spanning assumption if the vertex set of the host graph is sufficiently large.

AB - With sufficient minimum degree sum, Enomoto and Ota conjectured that for any selected set of vertices, there exists a spanning collection of disjoint paths, each starting at one of the selected vertices and each having a prescribed length. Using the Regularity Lemma, we prove that this claim holds without the spanning assumption if the vertex set of the host graph is sufficiently large.

KW - Degree sum

KW - Disjoint paths

KW - Regularity lemma

UR - https://digitalcommons.georgiasouthern.edu/math-sci-facpubs/220

UR - https://doi.org/10.1007/s00373-013-1351-7

U2 - 10.1007/s00373-013-1351-7

DO - 10.1007/s00373-013-1351-7

M3 - Article

SN - 0911-0119

VL - 30

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

ER -

Note on Enomoto and Ota’s Conjecture for Short Paths in Large Graphs

Abstract

Disciplines

Keywords

Access to Document

Other files and links

Cite this