Upper edge-connectivity bound for the rainbow disconnection number

From papers

Let GG be a connected graph. The upper edge-connectivity λ+(G)\lambda^+(G) is the maximum local edge-connectivity of GG, and rd(G)\operatorname{rd}(G) denotes the rainbow disconnection number of GG.

Rainbow disconnection bound. The conjecture states

λ+(G)rd(G)λ+(G)+1.\lambda^+(G)\leq \operatorname{rd}(G)\leq \lambda^+(G)+1.

This conjecture extends the bound known for connected regular graphs, complete multipartite graphs, and grid graphs. The paper proves it for many classes of graphs, but the general case is presented as open.

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

Xuqing Bai, Zhong Huang and Xueliang Li, “Bounds for the rainbow disconnection number of graphs”, arXiv:2003.13237 (2020).

Solutions 0

No solutions have been posted yet.