How can I construct “better” block graphs?

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];
];
Return[g];
];


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]:  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?

• 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? – Rahul May 30 '13 at 8:13
• 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. – Rahul May 30 '13 at 8:15
• @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). – Juho May 30 '13 at 17:46

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: 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",
For[i = 1, i <= (b - 1), ++i,
v = RandomChoice[VertexList[g]];
newblock =
UndirectedEdge @@@
Subsets[Union[{v},
Range[Max[VertexList[g]] + 1,
Max[VertexList[g]] + RandomInteger[{2, max-1}]]], {2}];

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