Arithmetical structures conjecture on extremal graph orders

Let GG be a simple graph with nn vertices. For a graph HH, let A(H)\mathcal{A}(H) denote its set of arithmetical structures, and let A(H)|\mathcal{A}(H)| be its cardinality. Let PnP_n and KnK_n be the path and complete graph, respectively, on nn vertices.

Arithmetical structures conjecture.

A(Pn)A(G)A(Kn).\big|\mathcal{A}(P_n)\big|\leq \big|\mathcal{A}(G)\big|\leq \big|\mathcal{A}(K_n)\big|.

This conjecture predicts that among simple graphs on nn vertices, the path minimizes and the complete graph maximizes the number of arithmetical structures. The paper presents computational evidence for the claim; no resolution is supplied here.

Sources & referencesView supporting material

Primary source

Carlos E. Valencia and R. R. Villagrán, “Algorithmic aspects of arithmetical structures”, arXiv:2101.05238 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.