Conjectured structure of quartic graphs with minimum spectral gap

Let GG be a connected quartic graph, meaning a connected 44-regular graph, on n11n\geq 11 vertices. Let M1M_1 denote the specified middle block and D1,D2,D4,D5D_1,D_2,D_4,D_5 the specified end blocks from the source. Choose non-negative integers qq and r<5r<5 satisfying

n11=5q+r.n-11=5q+r.

A graph is formed by concatenating qq middle blocks and the indicated end blocks.

Quartic minimum-gap conjecture. The connected quartic graph on n11n\geq 11 vertices with minimum spectral gap is the unique graph GG described as follows: GG consists of qq middle blocks M1M_1, with end blocks chosen according to rr. If r=0r=0, both end blocks are D4D_4; if r=1r=1, they are D4D_4 and D1D_1; if r=2r=2, both are D1D_1; if r=3r=3, they are D1D_1 and D2D_2; and if r=4r=4, they are D4D_4 and D5D_5.

This conjecture seeks the precise extremal structure, beyond the paper's theorem describing the general path-like block structure of quartic graphs with minimum spectral gap. The block definitions are supplied by figures elsewhere in the paper, and the assertion is not marked as resolved in the provided text.

Sources & referencesView supporting material

Primary source

M. Abdi, E. Ghorbani and W. Imrich, “Regular Graphs with Minimum Spectral Gap”, arXiv:1907.03733 (2020).

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.