ISSA ARTHUR E. IMPERATORE
SCHOOL OF SCIENCES AND ARTS
DEPARTMENT OF MATHEMATICAL SCIENCES SEMINARS
Universal Graphs


Dr. Michael Capalbo
DIMACS, Rutger University



Tuesday, February 28, 2006
4:00pm
Peirce 218


Abstract:  Let F be a family of graphs. We say that another graph H is *F-universal* if every graph in F is isomorphic to a subgraph of H--for example, if Fn is the family of graphs on n or fewer vertices, the complete graph on n vertices is Fn-universal. Besides being of theoretical interest, universal graphs also have applications to circuit design and network simulation. In particular, given a (finite) family F of (finite) graphs, it is of interest to construct a F-universal graph that has as few edges as possible. With this in mind, we first give an overview of the applications of universal graphs and previous work done. Next, for all integers n and k, let H(n,k) be the family of graphs on at most n vertices and with maximum degree at most k. We present a construction of an H(n,k)-universal graph that uses close to the minimum number of edges as possible.


Stevens Institute of Technology • Hoboken, NJ • (201) 216-5000