Small induced-universal graphs and compact implicit graph representations

We show that there exists a graph G with n · 2^{O(log* n)} nodes, where any forest with n nodes is a node-induced subgraph of G. Furthermore, the result implies the existence of a graph with n^k2^{O(log* n)} nodes that contains all n-node graphs of fixed arboricity k as node-induced subgraphs. We provide a lower bound of Ω(n^k) for the size of such a graph. The upper bound is obtained through a simple labeling scheme for parent queries in rooted trees.