From Wikipedia, the free encyclopedia - View original article

In graph theory, a branch of combinatorial mathematics, a **block graph** or **clique tree**^{[1]} is a type of undirected graph in which every biconnected component (block) is a clique.

Block graphs are sometimes erroneously called "Husimi trees" (after Kôdi Husimi),^{[2]} but that name more properly refers to cactus graphs, graphs in which every nontrivial biconnected component is a cycle.^{[3]}

Block graphs may be characterized as the intersection graphs of the blocks of arbitrary undirected graphs.^{[4]}

Block graphs are exactly the graphs for which, for every four vertices *u*, *v*, *x*, and *y*, the largest two of the three distances *d*(*u*,*v*) + *d*(*x*,*y*), *d*(*u*,*x*) + *d*(*v*,*y*), and *d*(*u*,*y*) + *d*(*v*,*x*) are always equal.^{[2]}^{[5]}

They also have a forbidden graph characterization as the graphs that do not have the diamond graph or a cycle of four or more vertices as an induced subgraph; that is, they are the diamond-free chordal graphs.^{[5]} They are also the Ptolemaic graphs (chordal distance-hereditary graphs) in which every two nodes at distance two from each other are connected by a unique shortest path,^{[2]} and the chordal graphs in which every two maximal cliques have at most one vertex in common.^{[2]}

A graph *G* is a block graph if and only if the intersection of every two connected subsets of vertices of *G* is empty or connected. Therefore, the connected subsets of vertices in a connected block graph form a convex geometry, a property that is not true of any graphs that are not block graphs.^{[6]} Because of this property, in a connected block graph, every set of vertices has a unique minimal connected superset, its closure in the convex geometry. The connected block graphs are exactly the graphs in which there is a unique induced path connecting every pair of vertices.^{[1]}

Block graphs are chordal and distance-hereditary. The distance-hereditary graphs are the graphs in which every two induced paths between the same two vertices have the same length, a weakening of the characterization of block graphs as having at most one induced path between every two vertices. Because both the chordal graphs and the distance-hereditary graphs are subclasses of the perfect graphs, block graphs are perfect.

Every tree is a block graph. Another class of examples of block graphs is provided by the windmill graphs.

Every block graph has boxicity at most two.^{[7]}

Block graphs are examples of pseudo-median graphs: for every three vertices, either there exists a unique vertex that belongs to shortest paths between all three vertices, or there exists a unique triangle whose edges lie on these three shortest paths.^{[7]}

The line graphs of trees are exactly the block graphs in which every cut vertex is incident to at most two blocks, or equivalently the claw-free block graphs. Line graphs of trees have been used to find graphs with a given number of edges and vertices in which the largest induced subgraph that is a tree is as small as possible.^{[8]}

If *G* is any undirected graph, the block graph of *G*, denoted *B*(*G*), is the intersection graph of the blocks of *G*: *B*(*G*) has a vertex for every biconnected component of *G*, and two vertices of *B*(*G*) are adjacent if the corresponding two blocks meet at an articulation vertex. If *K*_{1} denotes the graph with one vertex, then *B*(*K*_{1}) is defined to be the empty graph. *B*(*G*) is necessarily a block graph: it has one biconnected component for each articulation vertex of *G*, and each biconnected component formed in this way must be a clique. Conversely, every block graph is the graph *B*(*G*) for some graph *G*.^{[4]} If *G* is a tree, then *B*(*G*) coincides with the line graph of *G*.

The graph *B*(*B*(*G*)) has one vertex for each articulation vertex of *G*; two vertices are adjacent in *B*(*B*(*G*)) if they belong to the same block in *G*.^{[4]}

**Definition:** The block-cutpoint graph of a graph G is a bipartite graph H in which one partite set consists of the cut-vertices of G, and the other has a vertex b_{i} of each block B_{i} of G. We include vb_{i} as an edge of H if and only if v ∈ B_{i}.

- ^
^{a}^{b}Vušković, Kristina (2010), "Even-hole-free graphs: A survey",*Applicable Analysis and Discrete Mathematics***4**(2): 219–240, doi:10.2298/AADM100812027V. - ^
^{a}^{b}^{c}^{d}Howorka, Edward (1979), "On metric properties of certain clique graphs",*Journal of Combinatorial Theory, Series B***27**(1): 67–74, doi:10.1016/0095-8956(79)90069-8. **^**See, e.g., MR 0659742, a 1983 review by Robert E. Jamison of another paper referring to block graphs as Husimi trees; Jamison attributes the mistake to an error in a book by Behzad and Chartrand.- ^
^{a}^{b}^{c}Harary, Frank (1963), "A characterization of block-graphs",*Canadian Mathematical Bulletin***6**(1): 1–6, doi:10.4153/cmb-1963-001-x. - ^
^{a}^{b}Bandelt, Hans-Jürgen; Mulder, Henry Martyn (1986), "Distance-hereditary graphs",*Journal of Combinatorial Theory, Series B***41**(2): 182–208, doi:10.1016/0095-8956(86)90043-2. **^**Edelman, Paul H.; Jamison, Robert E. (1985), "The theory of convex geometries",*Geometriae Dedicata***19**(3): 247–270, doi:10.1007/BF00149365.- ^
^{a}^{b}Block graphs, Information System on Graph Class Inclusions. **^**Erdős, Paul; Saks, Michael; Sós, Vera T. (1986), "Maximum induced trees in graphs",*Journal of Combinatorial Theory, Series B***41**(1): 61–79, doi:10.1016/0095-8956(86)90028-6.