Computer Science/Discrete Mathematics Seminar I

Universal Graphs

Let F be a family of graphs. A graph H is *F-universal* if every GF is isomorphic to a subgraph of H. Besides being of theoretical interest, universal graphs have applications in chip design and network simulation. For any two positive integers n and k, let F(n,k) be the family of graphs on at most n vertices with maximum degree at most k. It has been known that any F(n,k)-universal graph must have Ωk(n22/k) edges. We show that this lower bound is tight up to a constant factor by presenting an explicit construction of a F(n,k)-universal graph H(n,k) with Ok(n22/k) edges, which is an improvement over the best previously known construction which uses a logarithmic (in n) factor more edges. We also present an efficient deterministic algorithm for finding a copy of each GF(n,k) in H(n,k). Joint work with Noga Alon.

Date & Time

May 08, 2006 | 11:15am – 12:15pm

Location

S-101

Affiliation

DIMACS