Block graph
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 graphs of the blocks of arbitrary undirected graphs.[1]
Block graphs have also been erroneously called "Husimi trees",[2] but that name more properly refers to cactus graphs, graphs in which every nontrivial biconnected component is a cycle.[3]
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.[4][2]
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 isometric subgraph,[4] as 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 as the chordal graphs in which every two maximal cliques have at most one vertex in common.[2]
A graph G is a connected block graph if and only if the intersection of every two connected subsets of vertices of G is again connected. Therefore, unlike in other types of graphs, the connected subsets of vertices in a connected block graph form a convex geometry.[5]
Block graphs of undirected graphs
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 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.[1] 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.[1]
References
- ^ a b c Harary, Frank (1963), "A characterization of block-graphs", Canadian Mathematical Bulletin, 6 (1): 1–6.
- ^ a b c d Howorka, Edward (1979), "On metric properties of certain clique graphs* 1", Journal of Combinatorial Theory, Series B, 27 (1): 67–74, doi:10.1016/0095-8956(79)90069-8.
- ^ See, e.g., MR0659742, a 1983 review by Robert E. Jamison of another paper referring to block graphs as Husimi trees; Jamison attributes the ambiguity to an error in a book by Behzad and Chartrand.
- ^ 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.