Geodesic
All Tight Descriptions of 3-Stars in 3-Polytopes with Girth 5
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 5-12.

Voir la notice de l'article provenant de la source Library of Science

Lebesgue (1940) proved that every 3-polytope P5 of girth 5 has a path of three vertices of degree 3. Madaras (2004) refined this by showing that every P5 has a 3-vertex with two 3-neighbors and the third neighbor of degree at most 4. This description of 3-stars in P5s is tight in the sense that no its parameter can be strengthened due to the dodecahedron combined with the existence of a P5 in which every 3-vertex has a 4-neighbor. We give another tight description of 3-stars in P5s: there is a vertex of degree at most 4 having three 3-neighbors. Furthermore, we show that there are only these two tight descriptions of 3-stars in P5s. Also, we give a tight description of stars with at least three rays in P5s and pose a problem of describing all such descriptions. Finally, we prove a structural theorem about P5s that might be useful in further research.
Keywords: 3-polytope, planar graph, structure properties, k -star 
@article{DMGT_2017_37_1_a0,
     author = {Borodin, Oleg V. and Ivanova, Anna O.},
     title = {All {Tight} {Descriptions} of {3-Stars} in {3-Polytopes} with {Girth} 5},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {5--12},
     publisher = {mathdoc},
     volume = {37},
     number = {1},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a0/}
}
TY  - JOUR
AU  - Borodin, Oleg V.
AU  - Ivanova, Anna O.
TI  - All Tight Descriptions of 3-Stars in 3-Polytopes with Girth 5
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 5
EP  - 12
VL  - 37
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a0/
LA  - en
ID  - DMGT_2017_37_1_a0
ER  - 
%0 Journal Article
%A Borodin, Oleg V.
%A Ivanova, Anna O.
%T All Tight Descriptions of 3-Stars in 3-Polytopes with Girth 5
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 5-12
%V 37
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a0/
%G en
%F DMGT_2017_37_1_a0
Borodin, Oleg V.; Ivanova, Anna O. All Tight Descriptions of 3-Stars in 3-Polytopes with Girth 5. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 5-12. http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a0/

[1] O.V. Borodin, Solution of Kotzig’s and Grünbaum’s problems on the separability of a cycle in a planar graph, Mat. Zametki 46 (1989) 9–12, in Russian.

[2] O.V. Borodin, Structural properties of planar maps with the minimal degree 5, Math. Nachr. 158 (1992) 109–117. doi:10.1002/mana.19921580108

[3] O.V. Borodin and D. Sanders, On light edges and triangles in planar graphs of minimal degree five, Math. Nachr. 170 (1994) 19–24. doi:10.1002/mana.19941700103

[4] O.V. Borodin and D.R. Woodall, Short cycles of low weight in normal plane maps with minimum degree 5, Discuss. Math. Graph Theory 18 (1998) 159–164. doi:0.7151/dmgt.1071

[5] O.V. Borodin and A.O. Ivanova, Describing 4 -stars at 5 -vertices in normal plane maps with minimum degree 5, Discrete Math. 313 (2013) 1710–1714. doi:10.1016/j.disc.2013.04.025

[6] O.V. Borodin, A.O. Ivanova and A.V. Kostochka, Every 3 -polytope with minimum degree 5 has a 6 -cycle with maximum degree at most 11, Discrete Math. 315–316 (2014) 128–134. doi:10.1016/j.disc.2013.10.021

[7] O.V. Borodin, A.O. Ivanova and D.R. Woodall, Light C4 and C5 in 3 -polytopes with minimum degree 5, Discrete Math. 334 (2014) 63–69. doi:10.1016/j.disc.2014.06.024

[8] O.V. Borodin, A.O. Ivanova and T.R. Jensen, 5 -stars of low weight in normal plane maps with minimum degree 5, Discuss. Math. Graph Theory 34 (2014) 539–546. doi:10.7151/dmgt.1748

[9] O.V. Borodin and A.O. Ivanova, Every 3 -polytope with minimum degree 5 has a 7 -cycle with maximum degree at most 15, Sibirsk. Mat. Zh. 56 (2015) 775–789, in Russian.

[10] B. Ferencová and T. Madaras, On the structure of polyhedral graphs with prescribed edge and dual edge weight, Acta Univ. M. Belii Ser. Math. 12 (2005) 13–18.

[11] B. Ferencová and T. Madaras, Light graph in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight, Discrete Math. 310 (2010) 1661–1675. doi:10.1016/j.disc.2009.11.027

[12] Ph. Franklin, The four-color problem, Amer. J. Math. 44 (1922) 225–236. doi:10.2307/2370527

[13] P. Hudák and T. Madaras, On doubly light triangles in plane graphs, Discrete Math. 313 (2013) 1978–1988. doi:10.1016/j.disc.2012.11.018

[14] S. Jendrol’ and T. Madaras, On light subgraphs in plane graphs with minimum degree five, Discuss. Math. Graph Theory 16 (1996) 207–217. doi:10.7151/dmgt.1035

[15] S. Jendrol’, T. Madaras, R. Soták and Zs. Tuza, On light cycles in plane triangulations, Discrete Math. 197–198 (1999) 453–467. doi:10.1016/S0012-365X(98)00254-4

[16] S. Jendrol’ and H.-J. Voss, Light subgraphs of graphs embedded in the plane—a survey, Discrete Math. 313 (2013) 406–421. doi:10.1016/j.disc.2012.11.007

[17] H. Lebesgue, Quelques conséquences simples de la formule d’Euler, J. Math. Pures Appl. 19 (1940) 27–43.

[18] T. Madaras and R. Soták, The 10-cycle C10 is light in the family of all plane triangulations with minimum degree five, Tatra Mt. Math. Publ. 18 (1999) 35–56.

[19] T. Madaras, On the structure of plane graphs of minimum face size 5, Discuss. Math. Graph Theory 24 (2004) 403–411. doi:10.7151/dmgt.1239

[20] T. Madaras, Two variations of Franklin’s theorem, Tatra Mt. Math. Publ. 36 (2007) 61–70.

[21] T. Madaras, R. Škrekovski and H.-J. Voss, The 7-cycle C7 is light in the family of planar graphs with minimum degree 5, Discrete Math. 307 (2007) 1430–1435. doi:10.1016/j.disc.2005.11.080

[22] E. Steinitz, Polyeder und Raumeinteilungen, Enzykl. Math. Wiss. 3 (1922) 1–139.

[23] P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413–426. doi:10.1007/BF01444968