The relaxed confusion-number bound conjecture for signed graphs

From papers

Let GG be a graph of order n1n \geq 1, let σ\sigma be a signing of GG, and let (G,σ)\ell(G,\sigma) denote the frustration index. Let Cr(G,σ)C_r(G,\sigma) denote the relaxed confusion number. The relaxed confusion-number bound conjecture. For every signed graph (G,σ)(G,\sigma),

Cr(G,σ)min{(G,σ),3n54}.C_r(G,\sigma) \leq \min\left\{\ell(G,\sigma),\left\lceil \frac{3n}{5}-4 \right\rceil\right\}.

This conjecture combines the proposed general confusion-number bound with the expectation that the relaxed confusion number is at most the frustration index. The paper gives supporting results for particular signed graphs but leaves the general assertion 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

Ligang Jin and Eckhard Steffen, “Information dissemination and confusion in signed networks”, arXiv:2407.09796 (2024).

Solutions 0

No solutions have been posted yet.