2021/08/31 by James Trimble, Trimble, James
Computer Science · Mathematics · #05C30 #Advanced Graph Theory Research #Chordal graph #Combinatorics #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #Discrete mathematics #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #G.2.2 #Graph #Graph Labeling and Dimension Problems #I.2.8 #Limits and Structures in Graph Theory #Mathematics #Vertex (graph theory) #acm:05C30 #cs.DM #math.CO #msc:05C30
paper · pdf · doi:10.48550/arxiv.2109.00075
22 pages, 13 figures, 4 tables. This version had additional results and more detailed explanations than the previous version
openalex publication_date 2021/08/31 · arxiv created 2021/10/25 · arxiv updated 2021/10/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We present exact and heuristic algorithms that find, for a given family of graphs, a graph that contains each member of the family as an induced subgraph. For 0 ≤ k ≤ 6, we give the minimum number of vertices f(k) in a graph containing all k-vertex graphs as induced subgraphs, and show that 16 ≤ f(7) ≤ 18. For 0 ≤ k ≤ 5, we also give the counts of such graphs, as generated by brute-force computer search. We give additional results for small graphs containing all trees on k vertices.