On vertex-disjoint paths in regular graphs

Jie Han

doi:10.37236/7109

On vertex-disjoint paths in regular graphs

Jie Han^*

^*Corresponding author for this work

Universidade de São Paulo

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

4 Citations (Scopus)

Abstract

Let ∊ (0, 1] be a real number and let n be a sufficiently large integer. We prove that every n-vertex cn-regular graph G contains a collection of [1/c] paths whose union covers all but at most o(n) vertices of G. The constant [1/c] is best possible when 1/c/∉ ℕ and off by 1 otherwise. Moreover, if in addition G is bipartite, then the number of paths can be reduced to [1/(2c)], which is best possible.

Original language	English
Article number	#P2.12
Journal	Electronic Journal of Combinatorics
Volume	25
Issue number	2
DOIs	https://doi.org/10.37236/7109
Publication status	Published - 27 Apr 2018
Externally published	Yes

Access to Document

10.37236/7109

Cite this

Han, J. (2018). On vertex-disjoint paths in regular graphs. Electronic Journal of Combinatorics, 25(2), Article #P2.12. https://doi.org/10.37236/7109

@article{453c30bd0fe3407d9edbe85fe5a0c16f,

title = "On vertex-disjoint paths in regular graphs",

abstract = "Let ∊ (0, 1] be a real number and let n be a sufficiently large integer. We prove that every n-vertex cn-regular graph G contains a collection of [1/c] paths whose union covers all but at most o(n) vertices of G. The constant [1/c] is best possible when 1/c/∉ ℕ and off by 1 otherwise. Moreover, if in addition G is bipartite, then the number of paths can be reduced to [1/(2c)], which is best possible.",

author = "Jie Han",

note = "Publisher Copyright: {\textcopyright} The authors.",

year = "2018",

month = apr,

day = "27",

doi = "10.37236/7109",

language = "English",

volume = "25",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "2",

}

TY - JOUR

T1 - On vertex-disjoint paths in regular graphs

AU - Han, Jie

PY - 2018/4/27

Y1 - 2018/4/27

N2 - Let ∊ (0, 1] be a real number and let n be a sufficiently large integer. We prove that every n-vertex cn-regular graph G contains a collection of [1/c] paths whose union covers all but at most o(n) vertices of G. The constant [1/c] is best possible when 1/c/∉ ℕ and off by 1 otherwise. Moreover, if in addition G is bipartite, then the number of paths can be reduced to [1/(2c)], which is best possible.

AB - Let ∊ (0, 1] be a real number and let n be a sufficiently large integer. We prove that every n-vertex cn-regular graph G contains a collection of [1/c] paths whose union covers all but at most o(n) vertices of G. The constant [1/c] is best possible when 1/c/∉ ℕ and off by 1 otherwise. Moreover, if in addition G is bipartite, then the number of paths can be reduced to [1/(2c)], which is best possible.

UR - http://www.scopus.com/inward/record.url?scp=85046156428&partnerID=8YFLogxK

U2 - 10.37236/7109

DO - 10.37236/7109

M3 - Article

AN - SCOPUS:85046156428

SN - 1077-8926

VL - 25

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 2

M1 - #P2.12

ER -

On vertex-disjoint paths in regular graphs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this