New Graphs with Thinly Spread Positive Combinatorial Curvature
New Graphs with Thinly Spread Positive Combinatorial Curvature
复制标题
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Jamie Sneddon;R. Nicholson
中科院分区：
文献类型：
--
作者：
Jamie Sneddon;R. Nicholson
平面图G的顶点v处的组合曲率定义为KG（v）= 1-v/2+ ∑ f v 1/|F|.根据欧拉公式，平面图的总曲率为2。2008年，张说，|V（G）|对于除棱柱和反棱柱之外的处处具有正组合曲率的平面图，< 580。我们改进了Réti，Bitay，and Kosztolányi在2005年发现的已知最大的这类图（138个顶点），给出了一个208个顶点的图，每个顶点都有正的组合曲率，且对任意v ∈ V（G），KG（v）∈ {1/13，1/66，1/132，1/858}.我们还给出了一个104个顶点的不可定向PCC图。
The combinatorial curvature at a vertex v of a plane graph G is defined as KG(v) = 1−v/2+ ∑ f∼v 1/|f |. As a consequence of Euler’s formula, the total curvature of a plane graph is 2. In 2008, Zhang showed that |V (G)| < 580 for plane graphs with everywhere positive combinatorial curvature other than prisms and antiprisms. We improve on the largest known such graph (on 138 vertices) found by Réti, Bitay, and Kosztolányi in 2005 by giving a graph on 208 vertices having positive combinatorial curvature at every vertex with KG(v) ∈ {1/13, 1/66, 1/132, 1/858} for all v ∈ V (G). We also give a non-orientable PCC graph with 104 vertices.