Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: light subgraph

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

On light subgraphs in plane graphs of minimum degree five

100%

Jendrol' S., Madaras T.

Discussiones Mathematicae Graph Theory

1996

tom 16

nr 2

207-217

A subgraph of a plane graph is light if the sum of the degrees of the vertices of the subgraph in the graph is small. It is well known that a plane graph of minimum degree five contains light edges and light triangles. In this paper we show that every plane graph of minimum degree five contains also light stars $K_{1,3}$ and $K_{1,4}$ and a light 4-path P₄. The results obtained for $K_{1,3}$ and P₄ are best possible.

5-Stars of Low Weight in Normal Plane Maps with Minimum Degree 5

88%

Borodin O. V., Ivanova A. O., Jensen T. R.

Discussiones Mathematicae Graph Theory

2014

tom 34

nr 3

539-546

It is known that there are normal plane maps M5 with minimum degree 5 such that the minimum degree-sum w(S5) of 5-stars at 5-vertices is arbitrarily large. In 1940, Lebesgue showed that if an M5 has no 4-stars of cyclic type (5, 6, 6, 5) centered at 5-vertices, then w(S5) ≤ 68. We improve this bound of 68 to 55 and give a construction of a (5, 6, 6, 5)-free M5 with w(S5) = 48

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

1 Borodin O. V.

1 Ivanova A. O.

1 Jendrol' S.

1 Jensen T. R.

1 Madaras T.

1 2014

1 1996

Wyniki wyszukiwania

On light subgraphs in plane graphs of minimum degree five

5-Stars of Low Weight in Normal Plane Maps with Minimum Degree 5