Article in volume
Authors:
Title:
Describing minor 5-stars in 3-polytopes with minimum degree 5 and no vertices of degree 6 or 7
PDFSource:
Discussiones Mathematicae Graph Theory 42(2) (2022) 535-548
Received: 2019-10-03 , Revised: 2019-12-13 , Accepted: 2019-12-13 , Available online: 2020-05-11 , https://doi.org/10.7151/dmgt.2323
Abstract:
In 1940, in attempts to solve the Four Color Problem, Henry
Lebesgue gave an approximate description of the neighborhoods of
5-vertices in the class $\bf P_5$ of 3-polytopes with minimum
degree 5. This description depends on 32 main parameters.
$(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,\infty)$, $(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)$.
Not many precise upper bounds on these parameters have been obtained as yet, even for restricted subclasses in $\bf P_5$. In 2018, Borodin, Ivanova, Kazak proved that every forbidding vertices of degree from 7 to 11 results in a tight description $(5,5,6,6,\infty)$, $(5,6,6,6,15)$, $(6,6,6,6,6)$. Recently, Borodin, Ivanova, and Kazak proved every $3$-polytope in $\bf P_5$ with no vertices of degrees 6, 7, and 8 has a $5$-vertex whose neighborhood is majorized by one of the sequences $(5,5,5,5,\infty)$ and $(5,5,10,5,12)$, which is tight and improves a corresponding description $(5,5,5,5,\infty)$, $(5,5,9,5,17)$, $(5,5,10,5,14)$, $(5,5,11,5,13)$ that follows from the Lebesgue Theorem. The purpose of this paper is to prove that every $3$-polytope with minimum degree 5 and no vertices of degree 6 or 7 has a $5$-vertex whose neighborhood is majorized by one of the ordered sequences $(5,5,5,5,\infty)$, $(5,5,8,5,14)$, or $(5,5,10,5,12)$.
$(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,\infty)$, $(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)$.
Not many precise upper bounds on these parameters have been obtained as yet, even for restricted subclasses in $\bf P_5$. In 2018, Borodin, Ivanova, Kazak proved that every forbidding vertices of degree from 7 to 11 results in a tight description $(5,5,6,6,\infty)$, $(5,6,6,6,15)$, $(6,6,6,6,6)$. Recently, Borodin, Ivanova, and Kazak proved every $3$-polytope in $\bf P_5$ with no vertices of degrees 6, 7, and 8 has a $5$-vertex whose neighborhood is majorized by one of the sequences $(5,5,5,5,\infty)$ and $(5,5,10,5,12)$, which is tight and improves a corresponding description $(5,5,5,5,\infty)$, $(5,5,9,5,17)$, $(5,5,10,5,14)$, $(5,5,11,5,13)$ that follows from the Lebesgue Theorem. The purpose of this paper is to prove that every $3$-polytope with minimum degree 5 and no vertices of degree 6 or 7 has a $5$-vertex whose neighborhood is majorized by one of the ordered sequences $(5,5,5,5,\infty)$, $(5,5,8,5,14)$, or $(5,5,10,5,12)$.
Keywords:
planar graph, structural properties, 3-polytope, 5-star, neighborhood
References:
- 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.
https://doi.org/10.1016/j.disc.2013.04.025 - O.V. Borodin and A.O. Ivanova, An analogue of Franklin's Theorem, Discrete Math. 339 (2016) 2553–2556.
https://doi.org/10.1016/j.disc.2016.04.019 - O.V. Borodin and A.O. Ivanova, Light and low $5$-stars in normal plane maps with minimum degree $5$, Sib. Math. J. 57 (2016) 470–475.
https://doi.org/10.1134/S0037446616030071 - O.V. Borodin and A.O. Ivanova, New results about the structure of plane graphs: a survey, AIP Conference Proceedings 1907 (2017) 030051.
https://doi.org/10.1063/1.5012673 - O.V. Borodin and A.O. Ivanova, Low $5$-stars in normal plane maps with minimum degree $5$, Discrete Math. 340 (2017) 18–22.
https://doi.org/10.1016/j.disc.2016.07.013 - O.V. Borodin and A.O. Ivanova, On light neighborhoods of $5$-vertices in $3$-polytopes with minimum degree $5$, Discrete Math. 340 (2017) 2234–2242.
https://doi.org/10.1016/j.disc.2017.04.012 - 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.
https://doi.org/10.7151/dmgt.1748 - O.V. Borodin, A.O. Ivanova and O.N. Kazak, Describing neighborhoods of $5$-vertices in $3$-polytopes with minimum degree $5$ and without vertices of degrees from $7$ to $11$, Discuss. Math. Graph Theory 38 (2018) 615–625.
https://doi.org/10.7151/dmgt.2024 - O.V. Borodin, A.O. Ivanova, O.N. Kazak and E.I. Vasil'eva, Heights of minor $5$-stars in $3$-polytopes with minimum degree $5$ and no vertices of degree $6$ and $7$, Discrete Math. 341 (2018) 825–829.
https://doi.org/10.1016/j.disc.2017.11.021 - O.V. Borodin, A.O. Ivanova and O.N. Kazak, Describing the neighborhood of $5$-stars in $3$-polytopes with minimum degree $5$ and no vertices of degree from $6$ to $8$, Discrete Math. 342 (2019) 2439–2444.
https://doi.org/10.1016/j.disc.2019.05.010 - O.V. Borodin and A.O. Ivanova, Light minor $5$-stars in $3$-polytopes with minimum degree $5$, Sib. Math. J. 60 (2019) 272–278.
https://doi.org/10.1134/S0037446619020071 - O.V. Borodin, A.O. Ivanova and D.V. Nikiforov, Low and light $5$-stars in $3$-polytopes with minimum degree $5$ and restrictions on the degrees of major vertices, Sib. Math. J. 58 (2017) 600–605.
https://doi.org/10.1134/S003744661704005X - O.V. Borodin, A.O. Ivanova and D.V. Nikiforov, Low minor $5$-stars in $3$-polytopes with minimum degree $5$ and no $6$-vertices, Discrete Math. 340 (2017) 1612–1616.
https://doi.org/10.1016/j.disc.2017.03.002 - 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.
https://doi.org/10.7151/dmgt.1071 - 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.
https://doi.org/10.1016/j.disc.2009.11.027 - Ph. Franklin, The four colour problem, Amer. J. Math. 44 (1922) 225–236.
https://doi.org/10.2307/2370527 - J. Harant and S. Jendrol', On the existence of specific stars in planar graphs, Graphs Combin. 23 (2007) 529–543.
https://doi.org/10.1007/s00373-007-0747-7 - A.O. Ivanova and D.V. Nikiforov, The structure of neighborhoods of $5$-vertices in plane triangulation with minimum degree $5$, Math. Notes of Yakutsk State University 20 (2013) 66–78, in Russian.
- 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 Projects 2015) 22–27, in Russian.
- S. Jendrol', A structural property of convex $3$-polytopes, Geom. Dedicata 68 (1997) 91–99.
https://doi.org/10.1023/A:1004993723280 - S. Jendrol' and T. Madaras, On light subgraphs in plane graphs of minimum degree five, Discuss, Math. Graph Theory 16 (1996) 207–217.
https://doi.org/10.7151/dmgt.1035 - 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.
- S. Jendrol' and H.-J. Voss, Light subgraphs of graphs embedded in the plane–-A survey, Discrete Math. 313 (2013) 406–421.
https://doi.org/10.1016/j.disc.2012.11.007 - H. Lebesgue, Quelques conséquences simples de la formule d'Euler, J. Math. Pures Appl. 19 (1940) 27–43.
- Y. Li, M. Rao and T. Wang, Minor stars in plane graphs with minimum degree five, Discrete Appl. Math. 257 (2019) 233–242.
https://doi.org/10.1016/j.dam.2018.10.019 - D.V. Nikiforov, The structure of neighborhoods of normal plane maps with minimum degree $5$, Math. Notes of North-Eastern Federal University 23 (2016) 56–66, in Russian.
- P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413–426.
https://doi.org/10.1007/BF01444968
Close