RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2015 Volume 56, Number 4, Pages 775–789 (Mi smj2677)

This article is cited in 5 papers

Each $3$-polytope with minimum degree $5$ has a $7$-cycle with maximum degree at most $15$

O. V. Borodina, A. O. Ivanovab

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk, Russia
b Ammosov North-Eastern Federal University, Yakutsk, Russia

Abstract: Let $\varphi_P(C_7)$ ($\varphi_T(C_7)$) be the minimum integer $k$ with the property that each $3$-polytope (respectively, each plane triangulation) with minimum degree $5$ has a $7$-cycle with all vertices of degree at most $k$. In 1999, Jendrol', Madaras, Soták, and Tuza proved that $15\le\varphi_T(C_7)\le17$. It is also known due to Madaras, Škrekovski, and Voss (2007) that $\varphi_P(C_7)\le359$.
We prove that $\varphi_P(C_7)=\varphi_T(C_7)=15$, which answers a question of Jendrol' et al. (1999).

Keywords: plane graph, structural properties, $3$-polytope, height.

UDC: 519.17

Received: 16.11.2014

DOI: 10.17377/smzh.2015.56.405


 English version:
Siberian Mathematical Journal, 2015, 56:4, 612–623

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024