3-Paths in Graphs with Bounded Average Degree

• Autorzy: Stanislav Jendrol′ , Mária Maceková , Mickaël Montassier , Roman Soták
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

average degree; structural property; 3-path; degree sequence

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 2
• Strony: 339-353

Daty

wydano

2016-05-01

otrzymano

2015-01-30

poprawiono

2015-07-07

zaakceptowano

2015-07-07

online

2016-04-15

Twórcy

autor

Stanislav Jendrol′

• Institute of Mathematics P.J. Šafárik University in Košice Jesenná 5, 04001 Košice, Slovakia

autor

Mária Maceková

• Institute of Mathematics P.J. Šafárik University in Košice Jesenná 5, 04001 Košice, Slovakia

autor

Mickaël Montassier

• University Montpellier 2 LIRMM, CNRS, UMR 5506, 161 Rue Ada 34095 Montpellier Cedex 5, France

autor

Roman Soták

• Institute of Mathematics P.J. Šafárik University in Košice Jesenná 5, 04001 Košice, Slovakia

Identyfikatory

DOI

10.7151/dmgt.1859