Connected Graphs with Specified Degree Sequences
by
Nisheeth Vishnoi
Georgia Institute of Technology
Coauthors: M.Mihail (Georgia Tech), D.Mubayi (Georgia Tech), P.Tetali (Georgia Tech)

A switch is the replacement of independent edges ab and cd in a simple graph G, by the edges ac and bd, if the latter edges were not present in G. The new graph has the same degree sequence as G.

Berge (1973) proved that given any two labeled graphs G, H with the same degree sequence, there is a sequence of switches that transforms G to H.

In this talk we present an extension of this result for the case when in addition G, H are connected. We will show that we can transform G to H by a sequence of switches such that all intermediate graphs are also connected. This gives a way of defining a Markov chain on the space of all connected realizations.

We will also present a simple algorithm ic solution to the following problem and a variant:

Given a sequence of nonnegative integers, find a "closest" sequence which corresponds to a degree sequence of a (connected) graph.

Together, the two results are useful in the context of the Internet and other networking applications, where random connected graphs whose degrees follow some statistical distribution are desired for simulations.

Some graph theoretic and algorithmic problems which remain open will also be presented.

Date received: April 23, 2001