Cycle Covering of Plane Triangulations

Hong-Jian Lai1, Hongyuan Lai2
1University of West Virginia Morgantown, WV 26506
2Wayne State University Detroit, MI 48202

Abstract

Bondy conjectures that if \(G\) is a \(2\)-edge-connected simple graph with \(n\) vertices, then at most \((2n-1)/{3}\) cycles in \(G\) will cover \(G\). In this note, we show that if \(G\) is a plane triangulation with \(n \geq 6\) vertices, then at most \((2n-3)/{3}\) cycles in \(G\) will cover \(G\).