AMRZ finite-exception conjecture for graph lines and bridges

Let GG be a connected graph, let (G)\ell(G) be the number of distinct graph-metric lines, and let \textscbr(G)\textsc{br}(G) denote the number of bridges of GG. A pendant edge is an edge incident with a vertex of degree one. AMRZ's finite-exception conjecture. There is a finite set of graphs F0\mathcal F_0 such that every connected graph GF0G\notin\mathcal F_0 either has a pendant edge or satisfies

(G)+\textscbr(G)G.\ell(G)+\textsc{br}(G)\geq |G|.

The paper proves the inequality for bipartite graphs except C4C_4 and K2,3K_{2,3}, but the conjecture for arbitrary connected graphs remains open.

Sources & referencesView supporting material

Primary source

Martín Matamala and José Zamora, “Lines in metric spaces: universal lines counted with multiplicity”, arXiv:1803.07154 (2018).

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.