5
$\begingroup$

I'm looking for an undirected graph $G$ which contains as induced subgraphs:

  • the six $4$-node connected graphs and,
  • the twenty one $5$-node connected graphs.

Ideally, I would also like it to be as small as possible (least number of nodes). If we take the union of these graphs, it has $6 \times 4+21 \times 5=129$ nodes. If we take the graphs and identify them at a point, it has $6 \times 4+21 \times 5-(6+21)+1=103$ nodes.

This would be helpful for testing our program for network motif detection program (NetMODE), which searches for connected induced subgraphs in networks.

If it helps, I've attached a picture of the graphs below:

4-node and 5-node connected graphs

  • 0
    Plus there is a graph with 8 vertices and 16 edges which contains 19 of the 21 5-vertex graphs, so I would conjecture that there will be a graph with 9 vertices which meets your needs...2011-10-24

2 Answers 2

9

Surprisingly, the answer is 7 vertices for all 4-vertex subgraphs and 9 vertices for all 5-vertex subgraphs. I checked all graphs with 8 vertices and this was the first one (and only one so far) with 9 vertices that I found:

A smallest graph which contains all 5-vertex subgraphs

This is the listing of each of the 21 different subgraphs with 5 vertices:

The 21 different connected subgraphs with 5 vertices

This is a graph which contains all the graphs with 4 vertices: All 4 vertex subgraphs exist

That is, $K_4 : \{a,b,c,d\}$, $K_4-e : \{ a,b,c,e \}$, $C_4 : \{a,b,e,f \}$, $P_4 : \{ c,d,e,f \}$, $K_{1,3} : \{b,e,f,g\}$ and the final one $\{b,c,d,f\}$.

And this is a graph with 10 vertices which contains all connected graphs with 5 vertices: All 5 vertex subgraphs exist

This is all of the different subgraphs of the latter graph: All 21 subgraphs listed

I'll continue the search for a 9 vertex graph overnight, but I'm now doubting it can exist. I can also update my answer with the Maple code if anyone is interested.

Even with the exponential increase in number of small subgraphs, there are so many graphs that I'd like to believe that there would be a graph with all subgraphs on $k$ vertices which isn't exponential in $k$. (but I would be wrong!)

  • 0
    Thanks for that! It is surprisingly small!2011-10-31
4

The size of a graph that contains all $k$-vertex subgraphs as induced subgraphs is exponential in $k$.

There are more than $2^{\binom{k}2}/k!$ graphs on $n$ vertices. So if $X$ is a graph on $n$ vertices that contains all $k$ vertex subgraphs as induced subgraphs then $$ \binom{n}{k} \ge 2^{\binom{k}2}/k! $$ and as $ \binom{n}{k} \le \frac{n^k}{k!} $ we have $$ n^k \ge 2^{\binom{k}2}. $$ So $$ k\, \log_2(n) \ge k(k-1)/2 $$ and therefore $n \ge 2^{(k-1)/2}$.

Let $p$ be a prime congruent to 1 mod 4. The vertices of the Paley graph are the integers mod $p$; two integers are adjacent if their difference is a square mod $p$. The Paley graph on $p$ vertices contains all graphs on $k$ vertices as induced subgraphs, where $k\approx c\,\log_2(p)$.