Induced universal graphs for families of small graphs

MaRDI QIDQ6376512zbMATH OpenFDO

Authors James Trimble

Publication date 31 August 2021

Mathematics Subject Classification ID

Enumeration in graph theory (05C30)

Abstract: 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 $0leqkleq6$, we give the minimum number of vertices $f(k)$ in a graph containing all $k$-vertex graphs as induced subgraphs, and show that $16leqf(7)leq18$. For $0leqkleq5$, 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.

This page was built for publication: Induced universal graphs for families of small graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6376512)