zbMATH — the first resource for mathematics

When is a graphical sequence stable? (English) Zbl 0819.05052
Frieze, Alan (ed.) et al., Random graphs. Volume 2. Based on papers presented at the fourth international seminar on random graphs and probabilistic methods in combinatorics, held in Poznań, Poland, August 7-11, 1989. Chichester: Wiley. Wiley-Interscience Publication. 101-115 (1992).
Let \(d\) be a sequence of \(n\) nonnegative integers, \(G(d)\) the set of labelled graphs with degree sequence \(d\), and \(N(G)= | G(d)|\). Let \(G'(d)\) be the union of the sets \(G(d')\) over all sequences \(d'\) obtainable from \(d\) by increasing one component of \(d\) by 1 and decreasing one other component of \(d\) by 1. A class of length-\(n\) sequences is \(P\)-stable if there is a polynomial \(p\) such that \(| G'(d)|\leq p(n)| G(d)|\) for every sequence \(d\) in the class. The class of length-\(n\) sequences \(d\) whose maximum component \(\Delta\) and minimum component \(\delta\) satisfy \(|\Delta- \delta+ 1|^ 2\leq 4\delta(n- \Delta- 1)\) is shown to be \(P\)-stable, as is a larger class of sequences satisfying an inequality involving the average component as well as \(\Delta\) and \(\delta\), and the above inequality is shown to be sharp. Several smaller classes of sequences are shown to be \(P\)-stable or not \(P\)-stable as special cases of these results. The significance of these results follows from two theorems in [the first two authors, Fast uniform generation of regular graphs, Theor. Comput. Sci. 73, No. 1, 91-100 (1990; Zbl 0694.68044)], which state that there are polynomial-time probabilistic algorithms which approximate random uniform generation of members of \(G(d)\) and asymptotic estimates for \(N(d)\) for any \(P\)-stable class of sequences \(d\). The authors note that all the known results about these two problems apply to \(P\)-stable classes of degree sequences and conjecture that these problems are intractable for more general classes of degree sequences.
For the entire collection see [Zbl 0811.00014].

05C75 Structural characterization of families of graphs
05C99 Graph theory
68R10 Graph theory (including graph drawing) in computer science