小圈二重覆盖三角剖分图(英文)

Small Circuit Double Covers of Near Triangulations

近三角剖分图是一连通平面图，其内面均为三角形，而其外面可能不是．图Ｇ的一个二重覆盖（ＣＤＣ）指它的一个圈族Ｃ，使得Ｇ的每条边恰属于Ｃ的两个元素．令Ｇ为一个具有ｎ个节点的２－连通平面图，Ｃ为Ｇ的一个ＣＤＣ．若｜Ｃ｜≤ｎ－１，则称Ｃ为Ｇ的一个小圈二重覆盖（ＳＣＤＣ）．本文证明每个近三角剖分图均存在一个ＳＣＤＣ．

A near triangulation is such a connected planar graph whose inner faces are all triangles but the outer face may be not. A circuit double cover (CDC) of a graph G is a collection C of circuits such that each edge of G belongs to two members of C exactly. Let G=(V,E) be a 2-connected planar graph of order n and C be a CDC of G . If |C|≤n-1, C is said to be a small circuit double cover (SCDC) of G . In this paper, we prove that every near triangulation admits an SCDC.