Geodesic
Every triangulated 3-polytope of minimum degree 4 has a 4-path of weight at most 27
O.V. Borodin1 ; A.O. Ivanova2
1Sobolev Institute of Mathematics
2Ammosov North-Eastern Federal University
The electronic journal of combinatorics, Tome 23 (2016) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

By $\delta$ and $w_k$ denote the minimum degree and minimum degree-sum (weight) of a $k$-vertex path in a given graph, respectively. For every 3-polytope, $w_2\le13$ (Kotzig, 1955) and $w_3\le21$ (Ando, Iwasaki, Kaneko, 1993), where both bounds are sharp. For every 3-polytope with $\delta\ge4$, we have sharp bounds $w_2\le11$ (Lebesgue, 1940) and $w_3\le17$ (Borodin, 1997).Madaras (2000) proved that every triangulated 3-polytope with $\delta\ge4$ satisfies $w_4\le31$ and constructed such a 3-polytope with $w_4=27$.We improve the Madaras bound $w_4\le31$ to the sharp bound $w_4\le27$.
DOI : 10.37236/5602
Classification : 05C10, 52B05
Mots-clés : plane graph, structural property, normal plane map, 4-path

O.V. Borodin  1   ; A.O. Ivanova  2

1 Sobolev Institute of Mathematics
2 Ammosov North-Eastern Federal University 
@article{10_37236_5602,
     author = {O.V. Borodin and A.O. Ivanova},
     title = {Every triangulated 3-polytope of minimum degree 4 has a 4-path of weight at most 27},
     journal = {The electronic journal of combinatorics},
     year = {2016},
     volume = {23},
     number = {3},
     doi = {10.37236/5602},
     zbl = {1351.05058},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/5602/}
}
TY  - JOUR
AU  - O.V. Borodin
AU  - A.O. Ivanova
TI  - Every triangulated 3-polytope of minimum degree 4 has a 4-path of weight at most 27
JO  - The electronic journal of combinatorics
PY  - 2016
VL  - 23
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/5602/
DO  - 10.37236/5602
ID  - 10_37236_5602
ER  - 
%0 Journal Article
%A O.V. Borodin
%A A.O. Ivanova
%T Every triangulated 3-polytope of minimum degree 4 has a 4-path of weight at most 27
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/5602/
%R 10.37236/5602
%F 10_37236_5602
O.V. Borodin; A.O. Ivanova. Every triangulated 3-polytope of minimum degree 4 has a 4-path of weight at most 27. The electronic journal of combinatorics, Tome 23 (2016) no. 3. doi: 10.37236/5602

Cité par Sources :