Logo image
Sign in
3-path in graphs with bounded average degree
Journal article   Open access   Peer reviewed

3-path in graphs with bounded average degree

Stanislav Jendrol, Mária Maceková, Mickaël Montassier and Roman Soták
Discussiones Mathematicae Graph Theory, Vol.36(2), pp.339-353
2016

Abstract

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 to contains a path of one of the types (Equation presented) Moreover, no parameter of this description can be improved.
url
Find in HALView
url
https://doi.org/10.7151/dmgt.1859View
Published (Version of record) Open

Metrics

1 Record Views

Details

Logo image