Refined weight of edges in normal plane maps

Ts Ch D. Batueva, O. V. Borodin, M. A. Bykov, A. O. Ivanova, O. N. Kazak, D. V. Nikiforov

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

2 Цитирования (Scopus)


The weight w(e) of an edge e in a normal plane map (NPM) is the degree-sum of its end-vertices. An edge e=uv is of type (i,j) if d(u)≤i and d(v)≤j. In 1940, Lebesgue proved that every NPM has an edge of one of the types (3,11), (4,7), or (5,6), where 7 and 6 are best possible. In 1955, Kotzig proved that every 3-connected planar graph has an edge e with w(e)≤13, which bound is sharp. Borodin (1989), answering Erdős’ question, proved that every NPM has either a (3,10)-edge, or (4,7)-edge, or (5,6)-edge. A vertex is simplicial if it is completely surrounded by 3-faces. In 2010, Ferencová and Madaras conjectured (in different terms) that every 3-polytope without simplicial 3-vertices has an edge e with w(e)≤12. Recently, we confirmed this conjecture by proving that every NPM has either a simplicial 3-vertex adjacent to a vertex of degree at most 10, or an edge of types (3,9), (4,7), or (5,6). By a k(ℓ)-vertex we mean a k-vertex incident with precisely ℓ triangular faces. The purpose of our paper is to prove that every NPM has an edge of one of the following types: (3(3),10), (3(2),9), (3(1),7), (4(4),7), (4(3),6), (5(5),6), or (5,5), where all bounds are best possible. In particular, this implies that the bounds in (3,10), (4,7), and (5,6) can be attained only at NPMs having a simplicial 3-, 4-, or 5-vertex, respectively.

Язык оригиналаанглийский
Страницы (с-по)2659-2664
Число страниц6
ЖурналDiscrete Mathematics
Номер выпуска11
СостояниеОпубликовано - 1 нояб. 2017


Подробные сведения о темах исследования «Refined weight of edges in normal plane maps». Вместе они формируют уникальный семантический отпечаток (fingerprint).