少圈二重覆盖平面近三角剖分图的生成元(英文)

On Generators of Planar Near-triangulations for Finding Small Circuit Double Covers

令Ｇ为一具有ｎ个节点的平面近三角剖分图，Ｃ为Ｇ的一个少圈二重覆盖（ＳＣＤＣ）．本文首先给出了Ｇ的一些生成元，由此可以得到Ｇ的一个ＳＣＤＣ．若Ｇ为一外平面近三角剖分图，得到 ｜Ｃ｜≤ｎ－２的一充分必要条件；若 Ｇ至少有一个内点，得到｜Ｃ｜≤ｎ－２的一充分条件．

Let G be a planar near-triangulation of order n and C be an SCDC(Small Circuit Double Cover) of G. In this paper, we firstly present some generators of G. Based on them we can find an SCDC C of G. Then, for an outer planar near-triangulation, a necessary and sufficient condition for |C| ≤ n -2 is obtained; for a planar near-triangulation with at least one interior vertex, we get a sufficient condition for |C|≤n -2.