Produção Nacional
Revisado por pares
Near-optimum Universal Graphs for Graphs with Bounded Degrees
2001; Springer Science+Business Media; Linguagem: Inglês
10.1007/3-540-44666-4_20
ISSN1611-3349
AutoresNoga Alon, Michael Capalbo, Yoshiharu Kohayakawa, Vojtěch Rödl, Andrzej Ruciński, Endre Szemerédi,
Tópico(s)Complexity and Algorithms in Graphs
ResumoLet $$ \mathcal{H} $$ be a family of graphs. We say that G is $$ \mathcal{H} $$ -universal if, for each H ∈ $$ \mathcal{H} $$ , the graph G contains a subgraph isomorphic to H. Let $$ \mathcal{H} $$ (k, n) denote the family of graphs on n vertices with maximum degree at most k. For each fixed k and each n sufficiently large, we explicitly construct an $$ \mathcal{H} $$ (k, n)-universal graph Γ(k, n) with O(n 2 - 2/k (log n)1+8/k ) edges. This is optimal up to a small polylogarithmic factor, as Ω(n 2-2/k ) is a lower bound for the number of edges in any such graph. En route, we use the probabilistic method in a rather unusual way. After presenting a deterministic construction of the graph Γ(k, n) we prove, using a probabilistic argument, that Γ(k, n) is $$ \mathcal{H} $$ (k, n)-universal. So we use the probabilistic method to prove that an explicit construction satisfies certain properties, rather than showing the existence of a construction that satisfies these properties.
Referência(s)