

A097911


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


3




OFFSET

1,2


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


LINKS

Table of n, a(n) for n=1..6.
N. Alon, Asymptotically optimal induced universal graphs, Geometric and Functional Analysis, 27(1):132, 2017.
Richard Rado, Universal graphs and universal functions, Acta Arith. 9 (1964), 331340.
J. Trimble, Induced universal graphs for families of small graphs, arXiv:2109.00075 [math.CO], 2021.


EXAMPLE

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.


CROSSREFS

Cf. A034797, A004401
Sequence in context: A288575 A091309 A027922 * A051611 A258028 A345427
Adjacent sequences: A097908 A097909 A097910 * A097912 A097913 A097914


KEYWORD

more,nonn


AUTHOR

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


EXTENSIONS

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


STATUS

approved



