Bounding the number of arithmetical structures on graphs

DOI10.1016/J.DISC.2021.112494zbMATH Open1468.05160arXiv2007.15100OpenAlexW3045974949MaRDI QIDQ2037577FDOQ2037577

Authors: Christopher Keyes, Tomer Reiter 

Publication date: 8 July 2021

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Let $G$ be a connected undirected graph on $n$ vertices with no loops but possibly multiedges. Given an arithmetical structure $(extbfr,extbfd)$ on $G$, we describe a construction which associates to it a graph $G^{\prime }$ on $n-1$ vertices and an arithmetical structure $(extbf{r}^{\prime },extbf{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.

Full work available at URL: https://arxiv.org/abs/2007.15100

Recommendations

• On arithmetical structures on complete graphs
• Algorithmic aspects of arithmetical structures
• Arithmetical structures on graphs
• Counting arithmetical structures on paths and cycles
• Arithmetical structures on paths with a doubled edge

zbMATH Keywords

critical grouparithmetical structureunit fraction representation

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Enumeration in graph theory (05C30) Continued fractions and generalizations (11J70) Arithmetic ground fields for curves (14H25) Rational numbers as sums of fractions (11D68)

Cites Work

• Unsolved problems in number theory
• Arithmetical graphs
• Counting arithmetical structures on paths and cycles
• The number of representations of rationals as a sum of unit fractions
• Title not available (Why is that?)
• A new algorithm for the expansion of Egyptian fractions
• On arithmetical structures on complete graphs
• Arithmetical structures on graphs
• Arithmetical structures on bidents
• The number of solutions of the Erdős-Straus equation and sums of \(k\) unit fractions

Cited In (12)

• On arithmetical structures on complete graphs
• Arithmetical structures on graphs
• Algorithmic aspects of arithmetical structures
• Title not available (Why is that?)
• Counting arithmetical structures on paths and cycles
• Title not available (Why is that?)
• Topological lower bounds for arithmetic networks
• Critical groups of arithmetical structures on star graphs and complete graphs
• Arithmetical structures on paths with a doubled edge
• \(\ell\)-adic images of Galois for elliptic curves over \(\mathbb{Q}\)(and an appendix with John Voight)
• Critical groups of arithmetical structures under a generalized star-clique operation
• Arithmetical structures on graphs with connectivity one

This page was built for publication: Bounding the number of arithmetical structures on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2037577)