A097911 Minimal order of a graph containing as induced subgraphs isomorphic copies of all graphs on n unlabeled nodes.

1, 3, 5, 8, 10, 14

Offset: 1

Author

Dan Schwarz (dan_schwarz(AT)hotmail.com), Sep 04 2004

Keywords

• more
• nonn

Comments

A graph that contains as induced subgraphs isomorphic copies of all graphs in a family F is called induced universal for F. - James Trimble, Nov 09 2021

16 <= a(7) <= 18 (Trimble, 2021). - James Trimble, Nov 09 2021

Examples

			a(3) = 5 as (P1 + K1)*K1 + K1 has 5 vertices and is easily seen minimal for 3. Here P1 is the path with one edge and K1 is an isolated vertex.
		

Links

• Noga Alon, Asymptotically optimal induced universal graphs, Geometric and Functional Analysis, 27(1):1-32, 2017.
• Richard Rado, Universal graphs and universal functions, Acta Arith. 9 (1964), 331-340.
• James Trimble, Induced universal graphs for families of small graphs, arXiv:2109.00075 [math.CO], 2021.
• James Trimble, Partitioning algorithms for induced subgraph problems, Ph.D. Thesis, Univ. of Glasgow (Scotland, 2023), 134.

Crossrefs

Cf. A034797, A004401

Extensions

a(5)-a(6) added by James Trimble, Nov 09 2021