Block graph

In graph theory, a block graph is a graph derived from a given graph that illustrates how the 2-connected components of each other relate to one another. ${\displaystyle G}$ ${\displaystyle G_{B}}$ ${\displaystyle G}$

definition

Let be a simple graph, as well as the set of its articulations and the set of its blocks . The graph is called the set of nodes and has an edge if and only if it holds for and that (i.e. if the articulation is part of the block) as a block graph of . ${\displaystyle G=(V,E)}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle V_{B}=A\cup B}$ ${\displaystyle (a,b)}$ ${\displaystyle a\in A}$ ${\displaystyle b\in B}$ ${\displaystyle a\in b}$ ${\displaystyle G_{B}}$ ${\displaystyle G}$

properties

• A block graph is always a bipartite graph and the sets are the partition classes of the graph. ${\displaystyle A,B}$
• The block graph of a graph is a forest . ${\displaystyle G_{B}}$ ${\displaystyle G}$
• ${\displaystyle G_{B}}$is tree (i.e. acyclic and connected) if and only if is connected. ${\displaystyle G}$

literature

• Reinhard Diestel: graph theory . Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 pages).