The conjectured swap-distance bounds for graphical degree sequences
For a degree sequence , let be the number of edges in any realization, and let
For realizations and of this degree sequence, write for the relevant discrepancy measure and for their swap-distance. The swap-distance bounds conjecture. The following inequalities hold:
- ;
- ;
- ; and
- .
These proposed bounds refine the preceding general upper bound on swap-distance and are intended to improve estimates for realizations of a common graphical degree sequence. The source provides no resolution of these statements.
References
- Péter L. Erdős, Zoltán Király and István Miklós, “On the swap-distances of different realizations of a graphical degree sequence”, arXiv:1205.2842 (2013).
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.