Premium
Sparse universal graphs for bounded‐degree graphs
Author(s) -
Alon Noga,
Capalbo Michael
Publication year - 2007
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20143
Subject(s) - combinatorics , mathematics , random regular graph , discrete mathematics , bounded function , degree (music) , expander graph , universality (dynamical systems) , random graph , graph , chordal graph , 1 planar graph , physics , mathematical analysis , quantum mechanics , acoustics
Let ℋ be a family of graphs. A graph T is ℋ‐universal if it contains a copy of each H ∈ℋ as a subgraph. Let ℋ( k , n ) denote the family of graphs on n vertices with maximum degree at most k . For all positive integers k and n , we construct an ℋ( k , n )‐universal graph T with $O_k(n^{2-{2 \over k}} \log ^{4 \over k} n)$ edges and exactly n vertices. The number of edges is almost as small as possible, as Ω( n 2‐2/ k ) is a lower bound for the number of edges in any such graph. The construction of T is explicit, whereas the proof of universality is probabilistic and is based on a novel graph decomposition result and on the properties of random walks on expanders. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007