Block graph

Encyclopedia

In graph theory

, a branch of combinatorial mathematics, a

(block) is a clique

. Block graphs may be characterized as the intersection graph

s of the blocks of arbitrary undirected graphs.

Block graphs have also been called

They are sometimes erroneously called "Husimi trees", but that name more properly refers to cactus graph

s, graphs in which every nontrivial biconnected component is a cycle.

and

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. They are also the Ptolemaic graphs (chordal

distance-hereditary graph

s) in which every two nodes at distance two from each other are connected by a unique shortest path, and the chordal graphs in which every two maximal cliques have at most one vertex in common.

A graph

subsets of vertices of

, a property that is not true of any graphs that are not block graphs. 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.

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 graph

s, block graphs are perfect.

Every tree

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

s.

Every block graph has boxicity

at most two.

Block graphs are examples of pseudo-median graph

s: 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.

The line graph

s 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.

of the blocks of

of

The graph

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, a branch of combinatorial mathematics, a

**block graph**is a type of undirected graph in which every biconnected componentBiconnected component

In graph theory, a biconnected component is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block tree of the graph. The blocks are attached to each other at shared vertices called cut vertices or articulation points...

(block) is a clique

Clique (graph theory)

In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...

. Block graphs may be characterized as the intersection graph

Intersection graph

In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...

s of the blocks of arbitrary undirected graphs.

Block graphs have also been called

**clique trees**.They are sometimes erroneously called "Husimi trees", but that name more properly refers to cactus graph

Cactus graph

In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, every edge in such a graph belongs to at most one simple cycle. Equivalently, every block is an edge or a cycle.-Properties:Cacti are outerplanar graphs...

s, graphs in which every nontrivial biconnected component is a cycle.

## Characterization

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.They also have a forbidden graph characterization as the graphs that do not have the diamond graph

Diamond graph

In the mathematical field of graph theory, the diamond graph is a planar undirected graph with 4 vertices and 5 edges. It consists of a complete graph K_4 minus one edge....

or a cycle of four or more vertices as an induced subgraph; that is, they are the diamond-free chordal graphs. They are also the Ptolemaic graphs (chordal

Chordal graph

In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...

distance-hereditary graph

Distance-hereditary graph

In graph-theoretic mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph...

s) in which every two nodes at distance two from each other are connected by a unique shortest path, and the chordal graphs in which every two maximal cliques have at most one vertex in common.

A graph

*G*is a block graph if and only if the intersection of every two connectedConnectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements which need to be removed to disconnect the remaining nodes from each other. It is closely related to the theory of network flow problems...

subsets of vertices of

*G*is empty or connected. Therefore, the connected subsets of vertices in a connected block graph form a convex geometryAntimatroid

In mathematics, an antimatroid is a formal system that describes processes in which a set is built up by including elements one at a time, and in which an element, once available for inclusion, remains available until it is included...

, a property that is not true of any graphs that are not block graphs. 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

Induced path

In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced subgraph of G. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge in G, and each two nonadjacent vertices in the...

connecting every pair of vertices.

## Related graph classes

Block graphs are chordalChordal graph

In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...

and distance-hereditary

Distance-hereditary graph

In graph-theoretic mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph...

. 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 graph

Perfect graph

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph....

s, block graphs are perfect.

Every tree

Tree (graph theory)

In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...

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

Windmill graph

In the mathematical field of graph theory, the windmill graph Wd is a simple undirected graph with n+1 vertices and nk/2 edges. It is defined for k ≥ 2 and n ≥ 2....

s.

Every block graph has boxicity

Boxicity

In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969.The boxicity of a graph is the minimum dimension in which a given graph can be represented as an intersection graph of axis-parallel boxes...

at most two.

Block graphs are examples of pseudo-median graph

Median graph

In mathematics, and more specifically graph theory, a median graph is an undirected graph in which any three vertices a, b, and c have a unique median: a vertex m that belongs to shortest paths between any two of a, b, and c.The concept of median graphs has long been studied, for instance by or ...

s: 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.

The line graph

Line graph

In graph theory, the line graph L of undirected graph G is another graph L that represents the adjacencies between edges of G...

s 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.

## Block graphs of undirected graphs

If*G*is any undirected graph, the block graph of*G*, denoted*B*(*G*), is the intersection graphIntersection graph

In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...

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*. If*G*is a tree, then*B*(*G*) coincides with the line graphLine graph

In graph theory, the line graph L of undirected graph G is another graph L that represents the adjacencies between edges of G...

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*.