logo

Block graphs

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.

VerticesNo. of graphs
11
21
32
44
59
622
759
8165
9496
101540
114960
1216390
1355408
14190572
15665699
162354932
178424025
1830424768
19110823984
20406734060
211502876903
225586976572
2320884546416
2478460794158
25296124542120
261122346648913
274270387848473
2816306781486064
2962476518448854
30240110929120323
Go to top
References

[1] T. Ekim, M. Shalom and M.A. Yirik, Generation of weighted trees, block trees and block graphs, arXiv preprint arXiv:2401.09764, 2024.


Copyright © 2010-2024 Ghent University & KU Leuven

Our website uses functional cookies to enhance your user experience. By using this site, you agree to our use of cookies. Learn more

Close