3
$\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

  • 1
    Each of the graphs with 4 nodes can be produced from one of the graphs of 5 nodes by removing a node, therefore any graph containing all 5 node connected graphs will also contain all 4 node connected graphs. If a 5 node graph has x arcs and x<9 then a 5-node graph with x+1 arcs can be made by removing a node of degree n and replacing with a node of degree n+1. Sometimes more than one x+1 graph can be made from one x graph, or more than one x graph makes the same x+1 graph, but at least I can deduce that the smallest G has at most 5*(21-(10-4))+(10-4)+5=86 nodes.2011-10-24
  • 0
    The smallest graph which contains all of the 4-vertex graphs has 7 vertices, and there are actually 77 such graphs (from a calculation with Maple).2011-10-24
  • 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

8

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
    I wouldn't mind seeing the maple code. Feel free to put it somewhere and link from the answer if it would clutter the answer.2011-10-24
  • 0
    Not sure how to make code look nice, but here's the base code. Call it for a maple graph G with: DrawGraph(fiveinlist(G, Glist5)); with(GraphTheory): Glist5:=[NonIsomorphicGraphs(5,output=graphs,outputform=graph,restrictto=connected)]: fiveinlist := proc (G, Glist) local S, bl, ts, l, ns; ts := []; for S in Glist do ns := 0; bl := 0; for lsubs in combinat[choose](Vertices(G), NumberOfVertices(Glist[1])) do if IsIsomorphic(InducedSubgraph(G, lsubs), S) then ns := 1; bl := lsubs end if end do; if ns = 1 then ts := [op(ts), InducedSubgraph(G, bl)] end if end do; RETURN(ts) end proc;2011-10-24
  • 0
    thanks. Do you have the code to make your specific G as well? (Sorry part of this is just to learn how to do reasonable things with graphs in maple.) Did you just search through random graphs on 10 vertices and are now searching 9 vertices exhaustively?2011-10-24
  • 0
    (ok, got the "four" one done at least)2011-10-24
  • 0
    I made that graph with: G5 := Graph(8); G5 := AddEdge(G5, {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {2, 8}, {3, 4}, {3, 5}, {4, 7}, {6, 7}, {7, 8}}); G5b := AddVertex(G5, 9, inplace = false); AddEdge(G5b, {{5, 9}, {8, 9}}); G5c := AddVertex(G5b, 10, inplace = false); AddEdge(G5c, {{1, 10}, {2, 10}, {3, 10}, {4, 10}});2011-10-24
  • 0
    G5 is the graph that had 8 vertices and 16 edges and 19 different 5-vertex induced subgraphs, and then I added vertex 9 to make G5b which contains $C_5$ and vertex 10 to finally make G5c which also contains a $K_5$; those were the two subgraphs which were missing from G5.2011-10-24
  • 0
    Thanks for that! It is surprisingly small!2011-10-31
3

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)$.