比利时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
****************************