小圈二重覆盖三角剖分图

摘要

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 eac h 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.%近三角剖分图是一连通平面图,其内面均为三角形,而其外面可能不是.图G的一个二重覆盖(CDC)指它的一个圈族C,使得G的每条边恰属于C的两个元素.令G为一个具有n个节点的2-连通平面图,C为G的一个CDC.若|C|≤n-1,则称C为G的一个小圈二重覆盖(SCDC).本文证明每个近三角剖分图均存在一个SCDC.