Least graph containing every connected graph with $m$ nodes as an induced subgraph

63 Views Asked by At
  • What is the smallest graph that contains every connected graph with $m$ nodes as an induced subgraph ?

    If the graph has $n$ nodes, there are $\binom{n}{m}$ (not necessariliy distinct) subgraphs with $m$ nodes. Since there are $2,6,21,112,853,11117,261080$ connected graphs with $3,4,5,6,7,8,9$ nodes, the lower bounds for the required number of vertices are $4,6,7,10,13,16,21$ because $\binom{n}{m}$ must be at least the number of connected graphs with $m$ nodes.

    But what is the minimal number of vertices required ?

    I found a similar question, where the cases $m=4$ and $m=5$ have been solved ($7$ and $9$ nodes) and it was stated that $n\ge 2^{\frac{m-1}{2}}$