Colloquia
Zoltan Toroczkai
CAM COLLOQUIUM
“On Realizing All Simple Graphs with a Given Degree Sequence”
Zoltan Toroczkai
Department of Physics
University of Notre Dame
Monday March 31, 2008
4:00PM in 127 Hayes-Healy Center
*TEA – 3:30PM in Math Lounge – 257 Hayes-Healy*
An exact algorithm is presented that constructs all simple graphs whose
degree sequence is identical to a given (graphical) sequence of integers.
We do this by first proving a theorem which gives the necessary and
sufficient conditions for the graphicality of a sequence of positive integers
constrained by a given (otherwise arbitrary) set of forbidden connections.
I discuss the applications of this algorithm to the problem of finding structural isomers of alkanes and network modeling in general.
