TY - GEN

T1 - Optimal universal graphs with deterministic embedding

AU - Alon, Noga

AU - Capalbo, Michael

PY - 2008/1/1

Y1 - 2008/1/1

N2 - Let H be a finite family of graphs. A graph G is Huniversal if it contains a copy of each H ∈ H as a subgraph. Let H(k, n) denote the family of graphs on n vertices with maximum degree at most k. For all admissible k and n, we construct an H(k, n)-universal graph G with at most Ck n2-2/k edges, where Ck is a constant depending only on k. This is optimal, up to the constant factor ck, as it is known that c′k,n22/k is a lower bound for the number of edges in any such graph. The construction of G is explicit, and there is an efficient deterministic algorithm for finding a copy of any given H ∈ H(k, n) in G.

AB - Let H be a finite family of graphs. A graph G is Huniversal if it contains a copy of each H ∈ H as a subgraph. Let H(k, n) denote the family of graphs on n vertices with maximum degree at most k. For all admissible k and n, we construct an H(k, n)-universal graph G with at most Ck n2-2/k edges, where Ck is a constant depending only on k. This is optimal, up to the constant factor ck, as it is known that c′k,n22/k is a lower bound for the number of edges in any such graph. The construction of G is explicit, and there is an efficient deterministic algorithm for finding a copy of any given H ∈ H(k, n) in G.

UR - http://www.scopus.com/inward/record.url?scp=58649088470&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58649088470&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:58649088470

SN - 9780898716474

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 373

EP - 378

BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms

PB - Association for Computing Machinery

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -