graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a branch of combinatorial mathematics, a block graph or clique tree. is a type of

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

in which every

biconnected component In graph theory, a biconnected component (sometimes known as a 2-connected component) is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks a ...

(block) is a

clique A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...

. Block graphs are sometimes erroneously called Husimi trees (after

Kôdi Husimi Kōji Husimi (June 29, 1909 – May 8, 2008, ja, 伏見康治) was a Japanese theoretical physicist who served as the president of the Science Council of Japan.. Husimi trees in graph theory, the Husimi Q representation in quantum mechanics, an ...

), but that name more properly refers to

cactus graph In graph theory, a cactus (sometimes called a cactus tree) is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or ...

s, graphs in which every nontrivial biconnected component is a cycle. Block graphs may be characterized as the

intersection graph In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...

s of the blocks of arbitrary undirected graphs..

Characterization

Block graphs are exactly the graphs for which, for every four vertices , , , and , the largest two of the three distances , , and are always equal... They also have a

forbidden graph characterization In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden ...

as the graphs that do not have the

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 minus one edge. The diamond graph has radius 1, diameter 2, girth 3, chromat ...

or a cycle of four or more vertices as an

induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Defini ...

; that is, they are the diamond-free chordal graphs. They are also the

Ptolemaic graph In graph theory, a Ptolemaic graph is an undirected graph whose shortest path distances obey Ptolemy's inequality, which in turn was named after the Greek astronomer and mathematician Ptolemy. The Ptolemaic graphs are exactly the graphs tha ...

s ( chordal

distance-hereditary graph In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph) is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any ...

s) in which every two nodes at distance two from each other are connected by a unique

shortest path In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between tw ...

, and the chordal graphs in which every two maximal cliques have at most one vertex in common. A graph is a block graph

if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicondi ...

the intersection of every two

connected Connected may refer to: Film and television * ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular'' * '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film * ''Connected'' (2015 TV ...

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

convex geometry In mathematics, convex geometry is the branch of geometry studying convex sets, mainly in Euclidean space. Convex sets occur naturally in many areas: computational geometry, convex analysis, discrete geometry, functional analysis, geometry of numbe ...

, 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 In the mathematical area of graph theory, an induced path in an undirected graph is a path that is an induced subgraph of . That is, it is a sequence of vertices in such that each two adjacent vertices in the sequence are connected by an edge ...

connecting every pair of vertices.

Related graph classes

Block graphs are chordal, distance-hereditary, and

geodetic Geodesy ( ) is the Earth science of accurately measuring and understanding Earth's figure (geometric shape and size), orientation in space, and gravity. The field also incorporates studies of how these properties change over time and equivale ...

. 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 In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph (clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is perfec ...

s, block graphs are perfect. Every

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

cluster graph In graph theory, a branch of mathematics, a cluster graph is a graph formed from the disjoint union of complete graphs. Equivalently, a graph is a cluster graph if and only if it has no three-vertex induced path; for this reason, the cluster gra ...

, or

windmill graph In the mathematical field of graph theory, the windmill graph is an undirected graph constructed for and by joining copies of the complete graph at a shared universal vertex. That is, it is a 1-clique-sum of these complete graphs. Propert ...

is a block graph. Every block graph has

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. That is, there mu ...

at most two.Block graphs
Information System on Graph Class Inclusions. Block graphs are examples of pseudo-

median graph In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices ''a'', ''b'', and ''c'' have a unique ''median'': a vertex ''m''(''a'',''b'',''c'') that belongs to shortest paths between each pair o ...

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 In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...

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. The block graphs in which every block has size at most three are a special type of

, a triangular cactus. The largest triangular cactus in any graph may be found in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

using an algorithm for the

matroid parity problem In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by as a common generalization of graph matching and matroid intersection. I ...

. Since triangular cactus graphs are

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

s, the largest triangular cactus can be used as an approximation to the largest planar subgraph, an important subproblem in planarization. As an

approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...

, this method has

approximation ratio An approximation is anything that is intentionally similar but not exactly equal to something else. Etymology and usage The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix ' ...

4/9, the best known for the maximum planar subgraph problem.

Block graphs of undirected graphs

If ''G'' is any undirected graph, the block graph of ''G'', denoted ''B''(''G''), is the

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''₁ denotes the graph with one vertex, then ''B''(''K''₁) is defined to be the

empty graph In the mathematical field of graph theory, the term "null graph" may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph"). Order-zero graph The order-zero graph, , is th ...

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

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

References

{{reflist Graph families Intersection classes of graphs Perfect graphs Trees (graph theory)