1. bookVolume 38 (2018): Issue 3 (August 2018)
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Describing Neighborhoods of 5-Vertices in 3-Polytopes with Minimum Degree 5 and Without Vertices of Degrees from 7 to 11

Published Online: 19 Jun 2018
Volume & Issue: Volume 38 (2018) - Issue 3 (August 2018)
Page range: 615 - 625
Received: 12 Jul 2016
Accepted: 13 Jan 2017
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

In 1940, Lebesgue proved that every 3-polytope contains a 5-vertex for which the set of degrees of its neighbors is majorized by one of the following sequences:

(6, 6, 7, 7, 7), (6, 6, 6, 7, 9), (6, 6, 6, 6, 11), (5, 6, 7, 7, 8), (5, 6, 6, 7, 12), (5, 6, 6, 8, 10), (5, 6, 6, 6, 17), (5, 5, 7, 7, 13), (5, 5, 7, 8, 10), (5, 5, 6, 7, 27), (5, 5, 6, 6, ∞), (5, 5, 6, 8, 15), (5, 5, 6, 9, 11), (5, 5, 5, 7, 41), (5, 5, 5, 8, 23), (5, 5, 5, 9, 17), (5, 5, 5, 10, 14), (5, 5, 5, 11, 13).

In this paper we prove that every 3-polytope without vertices of degree from 7 to 11 contains a 5-vertex for which the set of degrees of its neighbors is majorized by one of the following sequences: (5, 5, 6, 6, ∞), (5, 6, 6, 6, 15), (6, 6, 6, 6, 6), where all parameters are tight.

Keywords

MSC 2010

[1] V.A. Aksenov, O.V. Borodin and A.O. Ivanova, Weight of 3-paths in sparse plane graphs, Electron. J. Combin. 22 (2015) #P3.28.10.37236/4783Search in Google Scholar

[2] K. Ando, S. Iwasaki and A. Kaneko, Every 3-connected planar graph has a connected subgraph with small degree sum, Annual Meeting of Mathematical Society of Japan (1993).Search in Google Scholar

[3] 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.Search in Google Scholar

[4] O.V. Borodin, Joint generalization of the theorems of Lebesgue and Kotzig on the combinatorics of planar maps, Diskret. Mat. 3 (1991) 24–27, in Russian.Search in Google Scholar

[5] O.V. Borodin, Joint extension of two Kotzig’s theorems on 3-polytopes, Combinatorica 13 (1993) 121–125. doi:10.1007/BF0120279410.1007/BF01202794Search in Google Scholar

[6] O.V. Borodin, Minimal vertex degree sum of a 3-path in plane maps, Discuss. Math. Graph Theory 17 (1997) 279–284. doi:10.7151/dmgt.105510.7151/dmgt.1055Search in Google Scholar

[7] O.V. Borodin, Colorings of plane graphs: a survey, Discrete Math. 313 (2013) 517–539. doi:10.1016/j.disc.2012.11.01110.1016/j.disc.2012.11.011Search in Google Scholar

[8] O.V. Borodin and A.O. Ivanova, Describing (d − 2)-stars at d-vertices, d ≤ 5, in normal plane maps, Discrete Math. 313 (2013) 1700–1709. doi:10.1016/j.disc.2013.04.02610.1016/j.disc.2013.04.026Search in Google Scholar

[9] 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.02510.1016/j.disc.2013.04.025Search in Google Scholar

[10] 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.174810.7151/dmgt.1748Search in Google Scholar

[11] O.V. Borodin and A.O. Ivanova, An analogue of Franklin’s Theorem, Discrete Math. 339 (2016) 2553–2556. doi:10.1016/j.disc.2016.04.01910.1016/j.disc.2016.04.019Search in Google Scholar

[12] O.V. Borodin and A.O. Ivanova, Light and low 5-stars in normal plane maps with minimum degree 5, Sibirsk. Mat. Zh. 57 (2016) 596–602, in Russian. doi:10.1134/S003744661603007110.1134/S0037446616030071Search in Google Scholar

[13] 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:10.7151/dmgt.107110.7151/dmgt.1071Search in Google Scholar

[14] 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.02710.1016/j.disc.2009.11.027Search in Google Scholar

[15] Ph. Franklin, The four colour problem, Amer. J. Math. 44 (1922) 225–236. doi:10.2307/237052710.2307/2370527Search in Google Scholar

[16] J. Harant and S. Jendrol’, On the existence of specific stars in planar graphs, Graphs Combin. 23 (2007) 529–543. doi:10.1007/s00373-007-0747-710.1007/s00373-007-0747-7Search in Google Scholar

[17] A.O. Ivanova and D.V. Nikiforov, The structure of neighborhoods of 5-vertices in plane triangulation with minimum degree 5, Mat. Zam. YaSU 20(2) (2013) 66–78, in Russian.Search in Google Scholar

[18] A.O. Ivanova and D.V. Nikiforov, Combinatorial structure of triangulated 3-polytopes with minimum degree 5, in: Proceedings of the Scientific Conference of students, graduate students, and young researchers. XVII and XVIII Lavrent’ev’s reading, Yakutsk; Kirov: International Center for Research Project (2015) 22–27, in Russian.Search in Google Scholar

[19] S. Jendrol’, A structural property of convex 3-polytopes, Geom. Dedicata 68 (1997) 91–99. doi:10.1023/A:100499372328010.1023/A:1004993723280Search in Google Scholar

[20] S. Jendrol’, Paths with restricted degrees of their vertices in planar graphs, Czechoslovak Math. J. 49 (1999) 481–490. doi:10.1023/A:102241110056210.1023/A:1022411100562Search in Google Scholar

[21] S. Jendrol’ and M. Maceková, Describing short paths in plane graphs of girth at least 5, Discrete Math. 338 (2015) 149–158. doi:10.1016/j.disc.2014.09.01410.1016/j.disc.2014.09.014Search in Google Scholar

[22] S. Jendrol’, M. Maceková and R. Soták, Note on 3-paths in plane graphs of girth 4, Discrete Math. 338 (2015) 1643–1648. doi:10.1016/j.disc.2015.04.01110.1016/j.disc.2015.04.011Search in Google Scholar

[23] S. Jendrol’ and T. Madaras, On light subgraphs in plane graphs of minimal degree five, Discuss, Math. Graph Theory 16 (1996) 207–217. doi:10.7151/dmgt.103510.7151/dmgt.1035Search in Google Scholar

[24] S. Jendrol’ and T. Madaras, Note on an existence of small degree vertices with at most one big degree neighbour in planar graphs, Tatra Mt. Math. Publ. 30 (2005) 149–153.Search in Google Scholar

[25] 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.00710.1016/j.disc.2012.11.007Search in Google Scholar

[26] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat. Eas. SAV (Math. Slovaca) 5 (1955) 101–113.Search in Google Scholar

[27] A. Kotzig, From the theory of Eulerian polyhedra, Mat. Eas. SAV (Math. Slovaca) 13 (1963) 20–34, in Russian.Search in Google Scholar

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

[29] D.V. Nikiforov, The structure of neighborhoods of 5-vertices in normal plane maps with minimum degree 5, Mat. Zam. YaSU, 23 (2016) 56–66, in Russian.Search in Google Scholar

[30] O. Ore and M.D. Plummer, Cyclic coloration of plane graphs, in: Recent Progress in Combinatorics, W.T. Tutte, (Ed.), (Academic Press, New York, 1969) 287–293.Search in Google Scholar

[31] E. Steinitz, Polyeder und Raumeinteilungen, Enzykl. Math. Wiss. (Geometrie), 3AB 12 (1922) 1–139.Search in Google Scholar

[32] P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413–426. doi:10.1007/BF0144496810.1007/BF01444968Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo