printable pdf
比利时vs摩洛哥足彩 ,
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

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