Vernon1016

In graph theory, a decomposable graph is a type of graph which is used to model various mathematical concepts. These include modeling [[probability|probabilities in Bayesian statistics, and forming junction trees. Junction trees are a specialized type of a mathematical structure known as a tree. These junction trees can be used to solve problems such as graph coloring and constraint satisfaction.

Definitions

We say that $A$, $B$, and $S$, subsets of a graph $G$, form a proper decomposition of $G$, written as the ordered 3-tuple $(A,B,S)$ if the following statements all hold:

1. $A$, $B$, and $S$ are subsets of $G$ such that $V=A$∪$B$∪$S$, where $V$ is the vertex set of $G$.
2. The elements of $A$,$B$, and $S$ are distinct and share no common elements.
3. The set $S$ is a clique , which is a complete subset of vertices in $G$.
4. $S$ is a vertex separator in $G$.

A graph $G$ is said to be decomposable if either of the following holds:

1. $G$ is complete.
2. $G$ possesses a proper decomposition $(A,B,S)$ such that the induced subgraphs $G$_($A$∪$S$) and $G$_($B$∪$S$) are decomposable.

Properties and Facts

• All decomposable graphs are triangulated, or chordal. The converse is also true. This means that every cycle in a graph with length of at least 4 contains a chord, which is an edge connecting non-adjacent vertices.
• The removal of an edge (x,y), from a graph G, results in a decomposable graph if and only if the two vertices x and y are in exactly one clique.
• The addition of an edge (x,y), into a graph G, results in a decomposable graph if and only if x and y are unconnected, and contained in adjacent cliques in some junction tree of the graph G.

Examples

K4K4, the complete graph of 4 vertices is decomposable. All complete graphs are decomposable.

This graph is decomposable, since it can be split into two decomposable graphs using the center vertex as a clique which is a separator for the two subgraphs.

A more complex decomposable graph, which can be split into 3 complete subgraphs.