Bounding the number of arithmetical structures on graphs

Abstract

Let $G$ be a connected undirected graph on $n$ vertices with no loops but possibly multiedges. Given an arithmetical structure $(\text{r},\text{d})$ on $G$, we describe a construction which associates to it a graph $G^{\prime }$ on $n-1$ vertices and an arithmetical structure $({\text{r}}^{\prime },{\text{d}}^{\prime })$ on $G^{\prime }$. By iterating this construction, we derive an upper bound for the number of arithmetical structures on $G$ depending only on the number of vertices and edges of $G$. In the specific case of complete graphs, possibly with multiple edges, we refine and compare our upper bounds to those arising from counting unit fraction representations.

11 pages

References in corpus (2)

• On Arithmetical Structures on Complete Graphs
• Arithmetical Structures on Paths With a Doubled Edge

Cited by in corpus (3)

• Critical groups of arithmetical structures under a generalized star-clique operation
• Critical groups of arithmetical structures on star graphs and complete graphs
• Algorithmic aspects of arithmetical structures