Small Circuit Double Covers of Near-Triangulations
Liu Tongyin
Abstract：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.
Keywords：circuit double cover small circuit double cover tria ngulation
Publication Date：1999-01-01
Online Publishing Date：2025-08-15(First online date of this platform, not the publication date of the document)