On the Polyhedral Graphs with Positive Combinatorial Curvature

Réti, Tamás and Bitay, Enikő and Kosztolányi, Zsolt (2005) On the Polyhedral Graphs with Positive Combinatorial Curvature. ACTA POLYTECHNICA HUNGARICA, 2 (2). pp. 19-37. ISSN 1785-8860

Preview

Text Reti_4.pdf Download (502kB) | Preview

Abstract

The purpose of this article is to introduce a refinement of DeVos-Mohar conjecture in which the number of vertices of polyhedral graphs with positive combinatorial curvature, which are neither prisms, nor antiprisms, (PCC graphs) plays a significant role. According to the conjecture proposed by DeVos and Mohar, for the maximal vertex number Vmax of a PCC graph, the inequality VLB=120 ≤ Vmax ≤ VUB=3444 is fulfilled. In this paper we show that the lower bound VLB can be improved. The improved lower bound is VLB =138. It is also verified that there are no regular, vertex-homogenous PCC graphs with vertex number greater than 120. We conjecture that for PCC graphs the minimum value of combinatorial curvatures is not less than 1/380. If the conjecture is true this implies that the upper bound VUB is not greater than 760. Moreover, it is also conjectured that there are no PCC graphs having faces with side- number greater than 19, except two trivalent polyhedral graphs containing 20- and 22- sided faces, respectively.

Actions (login required)

Edit Item