On the Realizability of Edge-Girth Sequences

Abstract

The edge-girth of an edge $e$ in a simple connected graph is the length of a shortest cycle containing $e$, with $g_e=\infty$ if no such cycle exists, and the edge-girth sequence of a graph is the nondecreasing sequence of the edge-girths of its edges. We characterize the sequences that are realizable as the edge-girth sequence of a simple connected graph. A constant sequence $(g^{(m)})$ with $g$ finite and $m\ge 1$ is realizable if and only if $m=g$ or $m\ge \lceil 3g/2\rceil$. Otherwise, writing $S=S_0\uplus (g^{(m)})$, where $g$ is the maximum value of $S$ and $m$ its multiplicity, we prove that $S$ is realizable if and only if $S_0$ is realizable and $m$ lies in an explicit set determined by $g$ and by the maximum diameters of the graphs realizing $S_0$, alone or extended by fewer than $g$ edges of edge-girth $g$. The proof rests on a chaining lemma, which turns a shortest cycle of a realization into a lower bound on the maximum diameter of the realizations of a shorter sequence.