Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Light Graphs In Planar Graphs Of Large Girth

Peter HudákMária MacekováTomáš MadarasPavol Široczki — 2016

Discussiones Mathematicae Graph Theory

A graph H is defined to be light in a graph family 𝒢 if there exist finite numbers φ(H, 𝒢) and w(H, 𝒢) such that each G ∈ 𝒢 which contains H as a subgraph, also contains its isomorphic copy K with ΔG(K) ≤ φ(H, 𝒢) and ∑x∈V(K) degG(x) ≤ w(H, 𝒢). In this paper, we investigate light graphs in families of plane graphs of minimum degree 2 with prescribed girth and no adjacent 2-vertices, specifying several necessary conditions for their lightness and providing sharp bounds on φ and w for light K1,3...

3-Paths in Graphs with Bounded Average Degree

Stanislav Jendrol′Mária MacekováMickaël MontassierRoman Soták — 2016

Discussiones Mathematicae Graph Theory

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.

Page 1

Download Results (CSV)