Maximum-size biconnected digraphs of given radius

Let r52r\geq \frac52 and n2r+1n\geq 2r+1. Let Γ2r+1\overline{\Gamma}_{2r+1} be the digraph specified in the paper, and let Γn,2r,i,s\overline{\Gamma}_{n,2r,i,s} denote the family obtained by the indicated blow-ups, where 1i2r21\leq i\leq 2r-2 and 1sn2r1\leq s\leq n-2r. Radius extremal-structure conjecture. The biconnected digraphs of order nn and radius rr maximizing the size are formed by taking two blow-ups at consecutive, non-end vertices of Γ2r+1\overline{\Gamma}_{2r+1}. Furthermore, the extremal digraphs are exactly those of the form Γn,2r,i,s\overline{\Gamma}_{n,2r,i,s} where 1i2r21\leq i\leq 2r-2 and 1sn2r1\leq s\leq n-2r. This is presented as the radius analogue of the outradius conjecture; the small-order cases can have no simple uniform structure, whereas the stated range is conjectural.

Sources & referencesView supporting material

Primary source

Stijn Cambie, “Maximum size of digraphs of given radius”, arXiv:2201.00186 (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.