Optimal universal graphs with deterministic embedding

Noga Alon, Michael Capalbo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

24 Scopus citations

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 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 ck,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.

Original languageEnglish (US)
Title of host publicationProceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherAssociation for Computing Machinery
Pages373-378
Number of pages6
ISBN (Print)9780898716474
StatePublished - Jan 1 2008
Externally publishedYes
Event19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States
Duration: Jan 20 2008Jan 22 2008

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other19th Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CitySan Francisco, CA
Period1/20/081/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.