12 citations · 14 across the 3 of their papers we have counts for
3 papers
math.PR2005★ 12 cited
How likely is an i.i.d. degree sequence to be graphical?
Richard Arratia, Thomas M. Liggett
Given i.i.d. positive integer valued random variables D_1,...,D_n, one can ask whether there is a simple graph on n vertices so that the degrees of the vertices are D_1,...,D_n. We…
math.CO2002★ 2 cited
A Two-Variable Interlace Polynomial
Richard Arratia, Bela Bollobas, Gregory B. Sorkin
We introduce a new graph polynomial in two variables. This ``interlace'' polynomial can be computed in two very different ways. The first is an expansion analogous to the state spa…
math.CO2002
The Interlace Polynomial of a Graph
Richard Arratia, Bela Bollobas, Gregory B. Sorkin
Motivated by circle graphs, and the enumeration of Euler circuits, we define a one-variable ``interlace polynomial'' for any graph. The polynomial satisfies a beautiful and unexpec…