A graph is a block graph if it can be constructed from an undirected tree by replacing each edge with a clique. My method of generating "random" block graphs is as follows. The parameters are the number of blocks and the maximum size of any clique.

RandomBlockGraph[b_, max_] :=
  Module[{g = Graph[{}], L = Table[i, {i, 1, b*max}]},
    For[i = 1, i <= b, ++i,
      r = RandomInteger[{2, max}];
      h = IndexGraph[CompleteGraph[r], First[L]];
      L = Drop[L, r - 1];
      g = GraphUnion[g, h];

The function "glues" together cliques. The weakness is that right now, a vertex is joining at most 2 cliques. Here's a few examples of what the function spits out with RandomBlockGraph[3, 5]:

enter image description here

enter image description here

It would be nice if my function could say take a tree, and then actually replace every edge with a clique. This would make it possible to get as an output say a star graph on $n$ vertices, where every edge was replaced with a clique. The current function can't do this, since every vertex joins at most 2 cliques.

How can I modify (or write a better function) for generating block graphs such that a vertex can join more than just 2 cliques?

  • $\begingroup$ For each edge u <-> v in the tree, create max - 2 fresh vertices and attach them all to each other and to u and v? $\endgroup$
    – user484
    May 30, 2013 at 8:13
  • $\begingroup$ By the way, how do you get the 5-clique in Wikipedia's example by starting with a tree and replacing edges with cliques? I think your definition of block graph might be wrong. $\endgroup$
    – user484
    May 30, 2013 at 8:15
  • $\begingroup$ @RahulNarain That's a good point. The definition is from here, definition ii. That is another weakness of my current function (the current answer doesn't "fix" that either, but the mistake was mine in not mentioning it). $\endgroup$
    – Juho
    May 30, 2013 at 17:46

2 Answers 2


You can simply replace each edge of the tree with the edges of the click. The only point is to avoid repeated identifiers for the new vertices.

click[v1_, v2_, n_Integer] := First@# \[UndirectedEdge] Last@# & /@ Subsets[Join[{v1, v2}, {v1, v2, #} & /@ Range[n - 2]], {2}];
blockGraph[tree_Graph, max_Integer] := Graph@Flatten[click[First@#, Last@#, RandomInteger[{2, max}]] & /@ EdgeList[tree]];

Here is a sample call:

tree = Graph[{1 \[UndirectedEdge] 2, 1 \[UndirectedEdge] 3, 1 \[UndirectedEdge] 4, 2 \[UndirectedEdge] 5}];
blockGraph[tree, 5]

That converts this tree:


to this graph:

Block Graph


Here's another method. Let $G = K_n$, and choose a vertex $v \in V(G)$ uniformly and independently at random. Glue a new clique to $v$, and continue this process until the desired number of blocks have been obtained. This handles the problem mentioned by Rahul Narain in the comments: starting from a tree, one can't construct a 5-clique such as the one in Wikipedia's example.

RandomBlockGraph[max_, b_] :=
  Module[{g = 
     CompleteGraph[RandomInteger[{2, max}], VertexLabels -> "Name", 
      ImagePadding -> 20]},
   For[i = 1, i <= (b - 1), ++i,
    v = RandomChoice[VertexList[g]];
    newblock = 
     UndirectedEdge @@@ 
        Range[Max[VertexList[g]] + 1, 
         Max[VertexList[g]] + RandomInteger[{2, max-1}]]], {2}];
    g = EdgeAdd[g, newblock];

The usage is simple:

GraphPlot[RandomBlockGraph[3, 4], VertexLabeling -> True]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.