Edge‐maximal graphs on orientable and some nonorientable surfaces
Edge‐maximal graphs on orientable and some nonorientable surfaces
复制标题
DOI：
10.1002/jgt.22705
复制
发表时间：
2019-11
影响因子：
0.9
通讯作者：
James Davies;Florian Pfender
中科院分区：
文献类型：
--
作者：
James Davies;Florian Pfender
我们研究边极大的，不完全图的表面上，不三角化的表面。证明了在射影平面N1上不存在这样的图，K7 − e是Klein瓶N2上唯一的这样的图，K8 − E（C5）是环面S1上唯一的这样的图.与此相反，对于每个g ≥ 2，我们在亏格为g的可定向曲面Sg上构造了一个无限族这样的图，它们是缺少三角剖分的2 × g × 2边。
We study edge‐maximal, noncomplete graphs on surfaces that do not triangulate the surface. We prove that there is no such graph on the projective plane N 1 , K 7 − e is the unique such graph on the Klein bottle N 2 and K 8 − E ( C 5 ) is the unique such graph on the torus S 1 . In contrast to this for each g ≥ 2 we construct an infinite family of such graphs on the orientable surface S g of genus g , that are ⌊ g 2 ⌋ edges short of a triangulation.