Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Block graph
Summary
In graph theory, a branch of combinatorial mathematics, a block graph or clique tree
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), but that name more properly refers to cactus graphs, graphs in which every nontrivial biconnected component is a cycle.
Block graphs may be characterized as the intersection graphs of the blocks of arbitrary undirected graphs.
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 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 graphs) 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.
Block graphs are chordal, distance-hereditary, and geodetic. 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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.