1989/05/01 by Sandeep Bhatt, Fan Chung, Frank Thomson Leighton +1 · 75 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Interconnection Networks and Systems #Combinatorics #Mathematics #Bounded function #Degree (music) #Planar graph #Discrete mathematics #Graph #1-planar graph #Chordal graph #Physics
paper · doi:10.1137/0402014
published in SIAM Journal on Discrete Mathematics 2(2), 145-155 (Society for Industrial and Applied Mathematics)
openalex publication_date 1989/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
How small can a graph be that contains as subgraphs all trees on n vertices with maximum degree d? In this paper, this question is answered by constructing such universal graphs that have n vertices and bounded degree (depending only on d). Universal graphs with n vertices and O(nlog n) edges are also constructed that contain all bounded-degree planar graphs on n vertices as subgraphs. In general, it is shown that the minimum universal graph containing all bounded-degree graphs on n vertices with separators of size nα has O(n) edges if α < (1)/(2); O(nlog n) edges if α = (1)/(2); O(n2α ) edges if α > (1)/(2).