The maximum-spanning-tree conjecture for Moore graphs

From papers

Let GG be a simple graph, and let τ(G)\tau(G) denote its number of spanning trees. A kk-regular graph of girth gg with the minimum possible number of vertices is called a (k,g)(k,g)-cage; when it attains the Moore bound, it is a Moore graph. Moore-graph spanning-tree conjecture. Moore graphs have the maximum number of spanning trees among all simple graphs with the same number of vertices and edges.

This conjecture extends the observed extremal behavior of complete graphs, complete bipartite graphs, and the Petersen graph, but the source gives no resolution.

Progress summary

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

Sources & referencesView supporting material

Primary source

Dmitry Jakobson and Igor Rivin, “On some extremal problems in graph theory”, arXiv:math/9907050 (1999).

Solutions 0

No solutions have been posted yet.