Small Induced-Universal Graphs and Compact Implicit Graph Representations

We show that there exists a graph G with n /spl middot/ 2/sup 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/sup k/2/sup O(log* n)/ nodes that contains all n-node graphs of fixed arboricity k as node-induced subgraphs. We provide a lower bound of /spl Omega/(n/sup k/) for the size of such a graph. The upper bound is obtained through a simple labeling scheme for parent queries in rooted trees.

Authors

• Stephen Alstrup
• Theis Rauhe

Keywords

• Labeling
• Artificial intelligence
• Sparse matrices
• Testing
• Upper bound
• Tree graphs
• Terminology
• Labeling Strategy
• Less Than Or Equal
• Number Of Papers
• Tree Nodes
• Subtree
• Cluster Nodes
• Tree Size
• Unique Clusters
• Node Labels
• Unique Label
• Sparse Graph
• Big Cluster
• Partitional Clustering
• Planar Graphs
• Partial Labels
• Case Of Nodes
• Internal Cluster
• Family Of Graphs