Block graph
Encyclopedia
In graph theory
, a branch of combinatorial mathematics, a block graph is a type of undirected graph in which every biconnected component
(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 clique trees.
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.
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
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 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. 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 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 K1 denotes the graph with one vertex, then B(K1) 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 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.
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 component
Biconnected 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 connected
Connectivity (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 geometry
Antimatroid
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 K1 denotes the graph with one vertex, then B(K1) 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 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...
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.