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 ge = ∞ 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 ≥ 1 is realizable if and only if m = g or m ≥ ⌈ 3g/2 ⌉. Otherwise, writing S = S0 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 S0 is realizable and m lies in an explicit set determined by g and by the maximum diameters of the graphs realizing S0, 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.
Related
- Realizability of Cohomology Classes in Orthogonal Grassmannians
- A Quadratic Lower Bound for the Shield Number of the Stable Marriage Problem: Rearrangement, Extremal Construction, and Biclique Realizability
- Necessary and Sufficient Criteria for the Realizability of Kaleidocycles Composed of Six Congruent Isosceles Tetrahedra
- Differential Realizability of Static Control Allocation in Multirotors: An Impossibility under Nonredundant Full Actuation and a Pseudoinverse Obstruction under Redundant Actuation
- Equitable Partition Realizability for Dynamics-preserving and Privacy-aware Network Reconstruction
BibTeX
@misc{marey2026realizability,
title = {{On the Realizability of Edge-Girth Sequences}},
author = {Lilian Marey and Paul Hilaire and Charlotte Laclau},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.25629},
eprint = {2607.25629},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.25629},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the Realizability of Edge-Girth Sequences
AU - Lilian Marey
AU - Paul Hilaire
AU - Charlotte Laclau
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2607.25629
UR - https://arxiv.org/abs/2607.25629
AB - The edge-girth of an edge e in a simple connected graph is the length of a shortest cycle containing e, with g_e = ∞ 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 ≥ 1 is realizable if and only if m = g or m ≥ ⌈ 3g/2 ⌉. 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.
ER -