A block graph B(G) of a given graph G is the intersection graph of its blocks (i.e. 2-connected components). In other words, B(G) has a vertex for every block of G, and two vertices of B(G) are adjacent if the corresponding two blocks meet at a cut vertex. A graph is a block graph if it is isomorphic to B(G) for some graph G. Block graphs form a subclass of chordal graphs where each block consists of a complete graph.
Below the lists and counts of non-isomorphic connected block graphs up to 30 vertices are provided. These graphs were generated by Tinaz Ekim et al. using the algorithm BlockGraphGen described in [1]. The source code of this algorithm can be found here . The software can be utilised either for enumerating or generating block graphs.
The graph lists are currently only available in 'graph6' format. The larger files are compressed with gzip.
Vertices | No. of graphs |
---|---|
1 | 1 |
2 | 1 |
3 | 2 |
4 | 4 |
5 | 9 |
6 | 22 |
7 | 59 |
8 | 165 |
9 | 496 |
10 | 1540 |
11 | 4960 |
12 | 16390 |
13 | 55408 |
14 | 190572 |
15 | 665699 |
16 | 2354932 |
17 | 8424025 |
18 | 30424768 |
19 | 110823984 |
20 | 406734060 |
21 | 1502876903 |
22 | 5586976572 |
23 | 20884546416 |
24 | 78460794158 |
25 | 296124542120 |
26 | 1122346648913 |
27 | 4270387848473 |
28 | 16306781486064 |
29 | 62476518448854 |
30 | 240110929120323 |
[1] T. Ekim, M. Shalom and M.A. Yirik, Generation of weighted trees, block trees and block graphs, arXiv preprint arXiv:2401.09764, 2024.