Geodesic
3-Paths in Graphs with Bounded Average Degree
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 339-353

Voir la notice de l'article provenant de la source Library of Science

In this paper we study the existence of unavoidable paths on three vertices in sparse graphs. A path uvw on three vertices u, v, and w is of type (i, j, k) if the degree of u (respectively v, w) is at most i (respectively j, k). We prove that every graph with minimum degree at least 2 and average degree strictly less than m contains a path of one of the types Moreover, no parameter of this description can be improved.
Keywords: average degree, structural property, 3-path, degree sequence 
@article{DMGT_2016_36_2_a6,
     author = {Jendrol, Stanislav and Macekov\'a, M\'aria and Montassier, Micka\"el and Sot\'ak, Roman},
     title = {3-Paths in {Graphs} with {Bounded} {Average} {Degree}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {339--353},
     publisher = {mathdoc},
     volume = {36},
     number = {2},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a6/}
}
TY  - JOUR
AU  - Jendrol, Stanislav
AU  - Maceková, Mária
AU  - Montassier, Mickaël
AU  - Soták, Roman
TI  - 3-Paths in Graphs with Bounded Average Degree
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 339
EP  - 353
VL  - 36
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a6/
LA  - en
ID  - DMGT_2016_36_2_a6
ER  - 
%0 Journal Article
%A Jendrol, Stanislav
%A Maceková, Mária
%A Montassier, Mickaël
%A Soták, Roman
%T 3-Paths in Graphs with Bounded Average Degree
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 339-353
%V 36
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a6/
%G en
%F DMGT_2016_36_2_a6
Jendrol, Stanislav; Maceková, Mária; Montassier, Mickaël; Soták, Roman. 3-Paths in Graphs with Bounded Average Degree. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 339-353. http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a6/