TOPICS
Search

Block Graph


BlockGraphs

A block graph, also called a clique tree, is a simple graph in which every block is a complete graph. The numbers of unlabeled connected block graphs on n=1, 2, ... vertices are 1, 1, 2, 4, 9, 22, 59, 165, 496, ... (OEIS A035053).

Block graphs are chordal, distance-hereditary, perfect, and Ptolemaic. Every connected block graph is geodetic.

Classes of graphs which are block graphs include windmill graphs and trees.

A simple graph is a block graph iff, for every four vertices u, v, x, and y in the same connected component, the largest two of the sums

d_1=d(u,v)+d(x,y)
(1)
d_2=d(u,x)+d(v,y)
(2)
d_3=d(u,y)+d(v,x)
(3)

are equal (Howorka 1979), where d denotes the graph distance.


See also

Complete Graph, Graph Block

Explore with Wolfram|Alpha

References

House of Graphs. "Block Graphs." https://houseofgraphs.org/meta-directory/block-graphs.Howorka, E. "On Metric Properties of Certain Clique Graphs." J. Combin. Th. Ser. B 27, 67-74, 1979. https://doi.org/10.1016/0095-8956(79)90069-8.Sloane, N. J. A. Sequence A035053 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Block Graph

Cite this as:

Weisstein, Eric W. "Block Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BlockGraph.html

Subject classifications