Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Light Graphs In Planar Graphs Of Large Girth

100%

Hudák P., Maceková M., Madaras T., Široczki P.

Discussiones Mathematicae Graph Theory

2016

tom 36

nr 1

227-238

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 and C10.

3-Paths in Graphs with Bounded Average Degree

100%

Jendrol′ S., Maceková M., Montassier M., Soták R.

Discussiones Mathematicae Graph Theory

2016

tom 36

nr 2

339-353

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.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Maceková M.

1 Hudák P.

1 Jendrol′ S.

1 Madaras T.

1 Montassier M.

1 Soták R.

1 Široczki P.

2 2016

Wyniki wyszukiwania

Light Graphs In Planar Graphs Of Large Girth

3-Paths in Graphs with Bounded Average Degree