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\).

05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles