### Abstract

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 C_{k} ^{n2-2/k} edges, where C_{k} is a constant depending only on k. This is optimal, up to the constant factor c_{k}, as it is known that c^{′}_{k},n^{22/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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms |

Publisher | Association for Computing Machinery |

Pages | 373-378 |

Number of pages | 6 |

ISBN (Print) | 9780898716474 |

State | Published - Jan 1 2008 |

Externally published | Yes |

Event | 19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States Duration: Jan 20 2008 → Jan 22 2008 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 19th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country | United States |

City | San Francisco, CA |

Period | 1/20/08 → 1/22/08 |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Optimal universal graphs with deterministic embedding'. Together they form a unique fingerprint.

## Cite this

Alon, N., & Capalbo, M. (2008). Optimal universal graphs with deterministic embedding. In

*Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms*(pp. 373-378). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery.