An Extension of Kotzig’s Theorem

• Autorzy: Valerii A. Aksenov , Oleg V. Borodin , Anna O. Ivanova
• Języki publikacji: EN

Abstrakty

EN

In 1955, Kotzig proved that every 3-connected planar graph has an edge with the degree sum of its end vertices at most 13, which is tight. An edge uv is of type (i, j) if d(u) ≤ i and d(v) ≤ j. Borodin (1991) proved that every normal plane map contains an edge of one of the types (3, 10), (4, 7), or (5, 6), which is tight. Cole, Kowalik, and Škrekovski (2007) deduced from this result by Borodin that Kotzig’s bound of 13 is valid for all planar graphs with minimum degree δ at least 2 in which every d-vertex, d ≥ 12, has at most d − 11 neighbors of degree 2. We give a common extension of the three above results by proving for any integer t ≥ 1 that every plane graph with δ ≥ 2 and no d-vertex, d ≥ 11+t, having more than d − 11 neighbors of degree 2 has an edge of one of the following types: (2, 10+t), (3, 10), (4, 7), or (5, 6), where all parameters are tight.

Słowa kluczowe

EN

plane graph; normal plane map; structural property; weight

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 4
• Strony: 889-897

Daty

wydano

2016-11-01

otrzymano

2015-10-09

poprawiono

2016-01-06

zaakceptowano

2016-01-06

online

2016-10-21

Twórcy

autor

Valerii A. Aksenov

• Novosibirsk State University, Novosibirsk 630090,

autor

Oleg V. Borodin

• Institute of Mathematics Siberian Branch, Russian Academy of Sciences, Novosibirsk, 630090,

autor

Anna O. Ivanova

• Ammosov North-Eastern Federal University Yakutsk, 677000,

Identyfikatory

DOI

10.7151/dmgt.1904