On light neighborhoods of 5-vertices in 3-polytopes with minimum degree 5. (English) Zbl 1365.05057
Summary: Let \(w_\varDelta\) be the minimum integer \(W\) with the property that every 3-polytope with minimum degree 5 and maximum degree \(\varDelta\) has a vertex of degree 5 with the degree-sum (weight) of all vertices in its closed neighborhood at most \(W\).
Trivially, \(w_5 = 30\) and \(w_6 = 35\). H. Lebesgue [J. Math. Pures Appl., IX. Sér. 19, 27–43 (1940; Zbl 0024.28701)] proved \(w_\varDelta \leq \varDelta + 31\) for all \(\varDelta \geq 5\) and \(w_\varDelta \leq \varDelta + 27\) for \(\varDelta \geq 41\).
In 1998, the first Lebesgue’s result was improved by O. V. Borodin and D. R. Woodall [Discuss. Math., Graph Theory 18, No. 2, 159–164 (1998; Zbl 0927.05069)] to \(w_\varDelta \leq \varDelta + 30\). This bound is sharp for \(\varDelta = 7\) due to O. V. Borodin [Math. Nachr. 158, 109–117 (1992; Zbl 0776.05035)] and S. Jendrol’ and T. Madaras [Discuss. Math., Graph Theory 16, No. 2, 207–217 (1996; Zbl 0877.05050)], \(\varDelta = 9\) due to O. V. Borodin and A. O. Ivanova [Discrete Math. 313, No. 17, 1710–1714 (2013; Zbl 1277.05144)], \(\varDelta = 10\) due to Jendrol’ and Madaras [loc. cit.], and \(\varDelta = 12\) due to Borodin and Woodall [loc. cit.]. As for the second Lebesgue’s bound, O. V. Borodin et al. [Discuss. Math., Graph Theory 34, No. 3, 539–546 (2014; Zbl 1310.05063)] proved that \(w_\varDelta \leq \varDelta + 27\) for \(\varDelta \geq 28\), but \(w_{20} \geq 48\); the former fact was extended by O. V. Borodin and A. O. Ivanova [Sib. Math. J. 57, No. 3, 470–475 (2016); translation from Sib. Mat. Zh. 57, No. 3, 596–602 (2016; )Zbl 1345.05016] to \(w_\varDelta \leq \varDelta + 27\) for \(\varDelta \geq 23\).
The purpose of this paper is to prove \(w_\varDelta \leq \varDelta + 29\) whenever \(\varDelta \geq 13\) and show that \(w_8 = 38\), \(w_{11} = 41\), and \(w_{13} = 42\). Thus \(w_\varDelta\) remains unknown only for \(14 \leq \varDelta \leq 22\).
Trivially, \(w_5 = 30\) and \(w_6 = 35\). H. Lebesgue [J. Math. Pures Appl., IX. Sér. 19, 27–43 (1940; Zbl 0024.28701)] proved \(w_\varDelta \leq \varDelta + 31\) for all \(\varDelta \geq 5\) and \(w_\varDelta \leq \varDelta + 27\) for \(\varDelta \geq 41\).
In 1998, the first Lebesgue’s result was improved by O. V. Borodin and D. R. Woodall [Discuss. Math., Graph Theory 18, No. 2, 159–164 (1998; Zbl 0927.05069)] to \(w_\varDelta \leq \varDelta + 30\). This bound is sharp for \(\varDelta = 7\) due to O. V. Borodin [Math. Nachr. 158, 109–117 (1992; Zbl 0776.05035)] and S. Jendrol’ and T. Madaras [Discuss. Math., Graph Theory 16, No. 2, 207–217 (1996; Zbl 0877.05050)], \(\varDelta = 9\) due to O. V. Borodin and A. O. Ivanova [Discrete Math. 313, No. 17, 1710–1714 (2013; Zbl 1277.05144)], \(\varDelta = 10\) due to Jendrol’ and Madaras [loc. cit.], and \(\varDelta = 12\) due to Borodin and Woodall [loc. cit.]. As for the second Lebesgue’s bound, O. V. Borodin et al. [Discuss. Math., Graph Theory 34, No. 3, 539–546 (2014; Zbl 1310.05063)] proved that \(w_\varDelta \leq \varDelta + 27\) for \(\varDelta \geq 28\), but \(w_{20} \geq 48\); the former fact was extended by O. V. Borodin and A. O. Ivanova [Sib. Math. J. 57, No. 3, 470–475 (2016); translation from Sib. Mat. Zh. 57, No. 3, 596–602 (2016; )Zbl 1345.05016] to \(w_\varDelta \leq \varDelta + 27\) for \(\varDelta \geq 23\).
The purpose of this paper is to prove \(w_\varDelta \leq \varDelta + 29\) whenever \(\varDelta \geq 13\) and show that \(w_8 = 38\), \(w_{11} = 41\), and \(w_{13} = 42\). Thus \(w_\varDelta\) remains unknown only for \(14 \leq \varDelta \leq 22\).
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C07 | Vertex degrees |
| 05C22 | Signed and weighted graphs |
| 52B05 | Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) |
Citations:
Zbl 0024.28701; Zbl 0927.05069; Zbl 0776.05035; Zbl 0877.05050; Zbl 1277.05144; Zbl 1310.05063; Zbl 1345.05016References:
| [1] | Borodin, O. V., Structural properties of planar maps with minimal degree 5, Math. Nachr., 158, 1, 109-117 (1992) · Zbl 0776.05035 |
| [2] | Borodin, O. V.; Ivanova, A. O., Describing 4-stars at \(5\)-vertices in normal plane maps with minimum degree \(5\), Discrete Math., 313, 17, 1710-1714 (2013) · Zbl 1277.05144 |
| [3] | Borodin, O. V.; Ivanova, A. O., Light and low 5-stars in normal plane maps with minimum degree 5, Sib. Math. J., 57, 3, 470-475 (2016) · Zbl 1345.05016 |
| [4] | Borodin, O. V.; Ivanova, A. O.; Jensen, T. R., 5-stars of low weight in normal plane maps with minimum degree 5, Discuss. Math. Graph Theory, 34, 3, 539-546 (2014) · Zbl 1310.05063 |
| [5] | Borodin, O. V.; Woodall, D. R., Short cycles of low weight in normal plane maps with minimum degree 5, Discuss. Math. Graph Theory, 18, 2, 159-164 (1998) · Zbl 0927.05069 |
| [6] | Franklin, P., The four color problem, Amer. J. Math., 44, 225-236 (1922) · JFM 48.0664.02 |
| [7] | Jendrol’, S.; Madaras, T., On light subgraphs in plane graphs of minimum degree five, Discuss. Math. Graph Theory, 16, 2, 207-217 (1996) · Zbl 0877.05050 |
| [8] | Lebesgue, H., Quelques conséquences simples de la formule d’Euler, J. Math. Pures Appl., 19, 27-43 (1940) · JFM 66.0736.03 |
| [9] | Steinitz, E., Polyeder und Raumeinteilungen, Enzykl. Math. Wiss. (Geometrie), 3AB, 12, 1-139 (1922) |
| [10] | Wernicke, P., Über den kartographischen Vierfarbensatz, Math. Ann., 58, 413-426 (1904) · JFM 35.0511.01 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
