近三角剖分图的均衡二重少圈覆盖

摘要

A near-triangulation is such a connected planar graph whose inner faces are all triangles but the outer face may be not. Let G be a near-triangulation of order n and C be an SCDC (small circuit double cover)[2] of G. Letδ(C0) = min{max{l(cj)} - min{l(cj)} | C is an SCDC of G}.cj∈c cj∈cThen, Co is said to be an equilibrium SCDC of G. In this paper, we show that if G is anouter planar graph, δ(C0) ≤ 2, otherwise δ(Co) ≤ 4.%近三角剖分图是一连通平面图,其内面均为三角形而其外面可能不是.令G为一具有n个节点的近三角剖分图,C为G的一个小圈二重覆盖(SCDC)[2].令δ(C0)=min{max{l(cj)}-min{l(cj)}| C为G的一个SCDC},则Co称为G的均衡小圈二重覆盖.本文将证明:若G为外平面图,则δ(Co)≤2;否则δ(Co)≤4.