Geodesic
On vertex-disjoint paths in regular graphs
Jie Han1
1Universidade de São Paulo
The electronic journal of combinatorics, Tome 25 (2018) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Let $c\in (0, 1]$ be a real number and let $n$ be a sufficiently large integer. We prove that every $n$-vertex $c n$-regular graph $G$ contains a collection of $\lfloor 1/c \rfloor$ paths whose union covers all but at most $o(n)$ vertices of $G$. The constant $\lfloor 1/c \rfloor$ is best possible when $1/c\notin \mathbb{N}$ and off by $1$ otherwise. Moreover, if in addition $G$ is bipartite, then the number of paths can be reduced to $\lfloor 1/(2c) \rfloor$, which is best possible.
DOI : 10.37236/7109
Classification : 05C38
Mots-clés : regular graphs, paths

Jie Han  1

1 Universidade de São Paulo 
@article{10_37236_7109,
     author = {Jie Han},
     title = {On vertex-disjoint paths in regular graphs},
     journal = {The electronic journal of combinatorics},
     year = {2018},
     volume = {25},
     number = {2},
     doi = {10.37236/7109},
     zbl = {1391.05146},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7109/}
}
TY  - JOUR
AU  - Jie Han
TI  - On vertex-disjoint paths in regular graphs
JO  - The electronic journal of combinatorics
PY  - 2018
VL  - 25
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7109/
DO  - 10.37236/7109
ID  - 10_37236_7109
ER  - 
%0 Journal Article
%A Jie Han
%T On vertex-disjoint paths in regular graphs
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/7109/
%R 10.37236/7109
%F 10_37236_7109
Jie Han. On vertex-disjoint paths in regular graphs. The electronic journal of combinatorics, Tome 25 (2018) no. 2. doi: 10.37236/7109

Cité par Sources :