Refined weight of edges in normal plane maps
| Autor: | Anna O. Ivanova, Oleg V. Borodin, D. V. Nikiforov, Tsyndyma Chimit-Dordjievna Batueva, Mikhail A. Bykov, Olesy N. Kazak |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Vertex (graph theory)
Discrete mathematics Conjecture Degree (graph theory) Normal plane 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology Edge (geometry) Type (model theory) Lebesgue integration 01 natural sciences Theoretical Computer Science Planar graph Combinatorics symbols.namesake 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering symbols Discrete Mathematics and Combinatorics Mathematics |
| Zdroj: | Discrete Mathematics. 340:2659-2664 |
| ISSN: | 0012-365X |
| Popis: | 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 = u v 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, Ferencova 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 ( l ) -vertex we mean a k -vertex incident with precisely l 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect