|
Modelirovanie i Analiz Informatsionnykh Sistem, 2009, Volume 16, Number 1, Pages 16–23
(Mi mais45)
|
|
|
|
On the number of components in edge unfoldings of convex polyhedra
V. V. Astakhov, A. A. Gavrilyuk M. V. Lomonosov Moscow State University
Abstract:
In the theory of convex polyhedra there is a problem left unsolved which is sometimes called The Durer problem: Does every convex polyhedron have at least one connected unfolding? In this paper we consider a related problem: Find the upper bound $c(P)$ for the number of components in the edge unfolding of a convex polyhedron $P$ in terms of the number $F$ of faces. We showed that $c(P)$ does not exceed the cardinality of any dominating set in the dual graph $G(P)$ of the polyhedron $P$. Next we proved that there exists a dominating set in $G(P)$ of cardinality not more than $3F/7$. These two statements lead to an estimation $c(P)\le 3F/7$ that was proved in this work.
Keywords:
convex polyhedron, edge unfolding, dominating set.
Received: 15.09.2008
Citation:
V. V. Astakhov, A. A. Gavrilyuk, “On the number of components in edge unfoldings of convex polyhedra”, Model. Anal. Inform. Sist., 16:1 (2009), 16–23
Linking options:
https://www.mathnet.ru/eng/mais45 https://www.mathnet.ru/eng/mais/v16/i1/p16
|
Statistics & downloads: |
Abstract page: | 327 | Full-text PDF : | 149 | References: | 47 |
|