2026/07/28 by Lilian Marey, Paul Hilaire, Charlotte Laclau
Mathematics · #math.CO
The edge-girth of an edge e in a simple connected graph is the length of a shortest cycle containing e, with ge = ∞ if no such cycle exists. The edge-girth sequence of a graph is the nondecreasing sequence of edge-girth values over all its edges. We prove that a sequence S is realizable as the edge-girth sequence of a simple connected graph if and only if it satisfies a recursive criterion: writing S = S0 \uplus (g(m)) where g is the maximum edge-girth value of S with multiplicity m and S0 is the prefix subsequence, S is realizable if and only if S0 is realizable and the multiplicity m lies in a set entirely determined by g and the maximum diameter d^*S0 achievable by graphs realizing S0. We further determine d^*S for any realizable sequence: for constant sequences (g(m)), we obtain a closed-form formula when g is even and a recursive formula when g is odd. For general sequences, we provide a recursive algorithm computing d^*S together with explicit constructions of diameter-achieving graphs.