Universal graphs and induced‐universal graphs
- 1 September 1990
- journal article
- Published by Wiley in Journal of Graph Theory
- Vol. 14 (4) , 443-454
- https://doi.org/10.1002/jgt.3190140408
Abstract
We construct graphs that contain all bounded‐degree trees on n vertices as induced subgraphs and have only cn edges for some constant c depending only on the maximum degree. In general, we consider the problem of determining the graphs, so‐called universal graphs (or induced‐universal graphs), with as few vertices and edges as possible having the property that all graphs in a specified family are contained as subgraphs (or induced subgraphs). We obtain bounds for the size of universal and induced‐universal graphs for many classes of graphs such as trees and planar graphs. These bounds are obtained by establishing relationships between the universal graphs and the induced‐universal graphs.Keywords
This publication has 16 references indexed in Scilit:
- Universal Graphs for Bounded-Degree Trees and Planar GraphsSIAM Journal on Discrete Mathematics, 1989
- Expanding graphs contain all small treesCombinatorica, 1987
- On Universal Graphs for Spanning TreesJournal of the London Mathematical Society, 1983
- Universal caterpillarsJournal of Combinatorial Theory, Series B, 1981
- ON UNIVERSAL GRAPHSAnnals of the New York Academy of Sciences, 1979
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979
- On graphs which contain all small treesJournal of Combinatorial Theory, Series B, 1978
- Pancyclic graphs IJournal of Combinatorial Theory, Series B, 1971
- Graphs with forbidden subgraphsJournal of Combinatorial Theory, Series B, 1971
- On minimal n-universal graphsProceedings of the Glasgow Mathematical Association, 1965