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 that every graph with minimum degree at least 2 and average degree strictly less than in contains a path of one of the types (2, infinity , 2), (2, 8, 3), (4, 3, 5) if m = 15/4, (2, infinity , 2), (2,5,3), (3,2,4), (3,3,3) if m - 10/3, (2, 2, infinity), (2, 3, 4), (2, 5, 2) if m = 3, (2,2, 13), (2,3,3), (2,4,2) if m =14/5, (2, 2, i), (2 , 3, 2) if m = 3(i+1)/i+2 for 4 <= i <= 7, (2, 2, 3) if m = 12/5, and (2, 2, 2) if m = 9/4. Moreover, no parameter of this description can be improved. |
Year | DOI | Venue |
---|---|---|
2016 | 10.7151/dmgt.1859 | DISCUSSIONES MATHEMATICAE GRAPH THEORY |
Keywords | Field | DocType |
average degree,structural property,3-path,degree sequence | UVW mapping,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Structural property,Degree (graph theory),Frequency partition of a graph,Mathematics,Path graph,Bounded function | Journal |
Volume | Issue | ISSN |
36 | 2 | 1234-3099 |
Citations | PageRank | References |
2 | 0.40 | 0 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Stanislav Jendrol' | 1 | 283 | 38.72 |
M. Maceková | 2 | 12 | 2.70 |
Mickaël Montassier | 3 | 288 | 28.20 |
Roman Soták | 4 | 128 | 24.06 |