Optimal induced universal graphs for bounded-degree graphs

DOI10.1017/S0305004117000706zbMath1404.05032MaRDI QIDQ4614763

Rajko Nenadov, Noga Alon

Publication date: 31 January 2019

Published in: Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)

zbMATH Keywords

\(H\)-math-induced-universal graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Near-optimal induced universal graphs for cycles and paths, Quasipolynomiality of the Smallest Missing Induced Subgraph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Induced-universal graphs for graphs with bounded maximum degree
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• On induced-universal graphs for the class of bounded-degree graphs
• Ramanujan graphs
• Adjacency Labeling Schemes and Induced-Universal Graphs
• Universal graphs and induced-universal graphs
• Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs
• Implicat Representation of Graphs
• Near-Optimal Induced Universal Graphs for Bounded Degree Graphs
• Labeling Schemes for Bounded Degree Graphs
• On minimal n-universal graphs
• Sparse universal graphs for bounded‐degree graphs
• Universal graphs and universal functions
• SOME UNSOLVED PROBLEMS IN GRAPH THEORY