RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Sib. Èlektron. Mat. Izv.: Year: Volume: Issue: Page: Find

 Sib. Èlektron. Mat. Izv., 2016, Volume 13, Pages 584–591 (Mi semr695)

Discrete mathematics and mathematical cybernetics

Light neighborhoods of $5$-vertices in $3$-polytopes with minimum degree $5$

O. V. Borodina, A. O. Ivanovab

a Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia
b Ammosov North-Eastern Federal University, str. Kulakovskogo, 48, 677000, Yakutsk, Russia

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 $\mathbf{P}_5$ of $3$-polytopes with minimum degree $5$.
Given a $3$-polytope $P$, by $w(P)$ ($h(P)$) we denote the minimum degree-sum (minimum of the maximum degrees) of the neighborhoods of $5$-vertices in $P$.
A $5^*$-vertex is a $5$-vertex adjacent to four $5$-vertices. It is known that if a polytope $P$ in $\mathbf{P}_5$ has a $5^*$-vertex, then $h(P)$ can be arbitrarily large.
For each $P$ without vertices of degrees from $6$ to $9$ and $5^*$-vertices in $\mathbf{P}_5$, it follows from Lebesgue's Theorem that $w(P)\le 44$ and $h(P)\le 14$.
In this paper, we prove that every such polytope $P$ satisfies $w(P)\le 42$ and $h(P)\le 12$, where both bounds are tight.

Keywords: planar map, planar graph, $3$-polytope, structural properties, height, weight.

DOI: https://doi.org/10.17377/semi.2016.13.045

Full text: PDF file (656 kB)
References: PDF file   HTML file

Bibliographic databases:

Document Type: Article
Received May 18, 2016, published June 30, 2016
Language: English

Citation: O. V. Borodin, A. O. Ivanova, “Light neighborhoods of $5$-vertices in $3$-polytopes with minimum degree $5$”, Sib. Èlektron. Mat. Izv., 13 (2016), 584–591

Citation in format AMSBIB
\Bibitem{BorIva16} \by O.~V.~Borodin, A.~O.~Ivanova \paper Light neighborhoods of $5$-vertices in $3$-polytopes with minimum degree~$5$ \jour Sib. \Elektron. Mat. Izv. \yr 2016 \vol 13 \pages 584--591 \mathnet{http://mi.mathnet.ru/semr695} \crossref{https://doi.org/10.17377/semi.2016.13.045} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000407781100045} `

• http://mi.mathnet.ru/eng/semr695
• http://mi.mathnet.ru/eng/semr/v13/p584

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. O. V. Borodin, A. O. Ivanova, D. V. Nikiforov, “Low and light $5$-stars in $3$-polytopes with minimum degree $5$ and restrictions on the degrees of major vertices”, Siberian Math. J., 58:4 (2017), 600–605
2. O. V. Borodin, A. O. Ivanova, D. V. Nikiforov, “Describing neighborhoods of $5$-vertices in a class of $3$-polytopes with minimum degree $5$”, Siberian Math. J., 59:1 (2018), 43–49
3. O. V. Borodin, A. O. Ivanova, “Light 3-stars in sparse plane graphs”, Sib. elektron. matem. izv., 15 (2018), 1344–1352
•  Number of views: This page: 80 Full text: 22 References: 17