3-path in graphs with bounded average degree - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Discussiones Mathematicae Graph Theory Année : 2016

3-path in graphs with bounded average degree

Résumé

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.

Dates et versions

lirmm-01346642 , version 1 (19-07-2016)

Identifiants

Citer

Stanislav Jendrol, Mária Maceková, Mickaël Montassier, Roman Soták. 3-path in graphs with bounded average degree. Discussiones Mathematicae Graph Theory, 2016, 36 (2), pp.339-353. ⟨10.7151/dmgt.1859⟩. ⟨lirmm-01346642⟩
138 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More