Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Steve Butler

UCSD

Induced-universal graphs for graphs with bounded maximum degree

Abstract:

Given a family $\digamma$ of graphs, a graph $U$ is universal for $\bf{F}$ if every graph in $\bf{F}$ is a subgraph of $U$. We say that $U$ is induced-universal for $\bf {F}$ if every graph in $\bf{F}$ is an {\it induced} subgraph of $U$. Recently Alon and Capalbo gave a construction for a universal graph for the family $\bf{F}$ of graphs on $n$ vertices with bounded degree which is within a constant factor of the best possible. We give a construction for an induced-universal graph for the family of graphs on $n$ vertices with degree at most $r$, which has $Cn^{\lfloor (r+1)/2\rfloor}$ vertices and $Dn^{2\lfloor (r+1)/2\rfloor -1}$ edges, where $C$ and $D$ are constants depending only on $r$. This construction is nearly optimal when $r$ is even in that such an induced-universal graph must have at least $cn^{r/2}$ vertices for some $c$ depending only on $r$. Our construction is explicit in that no probabilistic tools are needed to show that the graph exists or that a given graph is induced-universal. We extend our construction to multigraphs and directed graphs with bounded degree, and also graphs with bounded arboricity.

Host:

April 4, 2006

4:00 PM

AP&M 7321

****************************