Cyclic Base Orderings in Some Classes of Graphs

Abstract

A cyclic base ordering of a connected graph $G$ is a cyclic ordering of $E(G)$ such that every $|V(G)|–1$ cyclically consecutive edges form a spanning tree of $G$. Let $G$ be a graph with $E(G)\ne \mathrm{\varnothing }$ and let $\omega (G)$ denote the number of components in $G$. The invariants $d(G)$ and $\gamma (G)$ are respectively defined as $d(G)=\frac{|E(G)|}{|V(G)|–\omega (G)}$ and $\gamma (G)=\text{max}\{d(H)\}$, where $H$ runs over all subgraphs of $G$ with $E(H)\ne \mathrm{\varnothing }$. A graph $G$ is uniformly dense if $d(G)=\gamma (G)$. Kajitani et al. [8] conjectured in 1988 that a connected graph $G$ has a cyclic base ordering if and only if $G$ is uniformly dense. In this paper, we show that this conjecture holds for some classes of uniformly dense graphs.