# zbMATH — the first resource for mathematics

Equilibrium small circuit double covers of near-triangulations. (English) Zbl 0996.05038
Let $${\mathcal{C}}$$ be the collection of circuits of an $$n$$-vertex graph $$G$$. If each edge of $$G$$ belongs to exactly two members of $${\mathcal{C}}$$, then $${\mathcal{C}}$$ is called a circuit double cover of $$G$$. If, moreover, $$|{\mathcal{C}}|\leq n-1$$, then $${\mathcal{C}}$$ is called a small circuit double cover of $$G$$.
In [OR Trans 2(4) (1999)] and [J. Northern Jiaotong Uni. 24(2) (2000)] the authors proved that every near-triangulation $$G$$ admits a small circuit double cover (SCDC) $${\mathcal{C}}$$, and, for outerplanar near-triangulations, $$|{\mathcal{C}}|\leq n-2$$ if and only if $$G$$ contains an interior triangle. In the paper under review, they study the parameter $\delta({\mathcal{C}}_0) = \min\{ \max_{c_j \in {\mathcal{C}}} \{l(c_j)\} - \min_{c_j \in {\mathcal{C}}} \{l(c_j)\} |\;{\mathcal{C}} \text{ is an SCDC of } G \}.$ The authors prove that, for a near-triangulation $$G$$, if $$G$$ is an outerplanar graph, then $$\delta({\mathcal{C}}_0) = 2$$, and if $$G$$ has at least one interior vertex, then $$\delta({\mathcal{C}}_0) \leq 4$$.

##### MSC:
 05C10 Planar graphs; geometric and topological aspects of graph theory 05C38 Paths and cycles
##### Keywords:
small circuit double cover; near-triangulation