1
$\begingroup$

If a graph is chordal, then it is a simple graph that contains no induced cycle of length 4 or more.

A simplicial decomposition is a sequence ($V_1, V_2, ..., V_k$) of maximal cliques of $G$ such that $V_j \cap$ ($\bigcup_{i=1}^{j-1}$ $V_i$) is a clique of $G$, 2 $\le j \le k$.

($G$ is a connected chordal graph such that $V_1$ is a maximal clique)

There is a corollary from this site that states that every chordal graph has simplicial decomposition, but why? What is the proof or reasoning for that?


Also, does this apply for graphs with simplicial order (i.e. every chordal graph has simplicial order)?

Note that the simplicial order of $G$ is an enurmeration $v_1, v_2, ..., v_n$ of its vertices where $v_i$ is a simplicial vertex of $G$[{$v_i, v_{i+1}, ...,v_n$}], 1 $\le i \le n$.

(and a simplicial vertex of a graph is a vertex whose neighbours induce a clique)

$\endgroup$
  • $\begingroup$ Yes see Bondy & Murty 9.20. Suppose we have a minimal vertex cut, which must be a clique... $\endgroup$ – A.S May 8 '17 at 2:43
0
$\begingroup$

The definition of simplicial decomposition that you're using makes it harder to see the connection.

The link you give proves that every chordal graph $G$ has a simplicial vertex $v$. We can easily use this to build a simplicial order $(v_1, v_2, \dots, v_n)$. Begin by letting $v_1$ be a simplicial vertex of $G$. Then $G - \{v_1\}$ is still chordal, so it also has a simplicial vertex: let $v_2$ be a simplicial vertex of $G - \{v_1\}$. Repeat, taking $v_2$ to be a simplicial vertex of $G - \{v_1, v_2\}$, and in general taking $v_k$ to be a simplicial vertex of $G - \{v_1, \dots, v_{k-1}\}$.

A similar idea gives a simplicial decomposition under the definition you're using. Instead of constructing the cliques in the order $(V_1, \dots, V_k)$, I'll construct them in the reverse order $(W_1, \dots, W_k) = (V_k, \dots, V_1)$.

Let $v_1$ be a simplicial vertex of $G$, and let $W_1$ be the clique of $v_1$ and all its neighbors. Then construct $G_2$ from $G$ as follows:

  • Remove $v_1$ from $G$.
  • Remove all other vertices which have no neighbors outside $W_1$.

Note that $W_1 \cap E(G_2)$ is a clique: it is the clique formed by all vertices of $W_1$ that we do not remove at this step.

Since $G_2$ is still chordal, we can repeat this process, getting cliques $W_2, \dots, W_k$ until there are no more vertices left.

We check they are all maximal. $W_i$ consists of $v_i$ and all neighbors of $v_i$ in $G_i$, so it can't be extended by any other vertices of $G_i$. But it can't be extended by vertices previously removed, either: by definition, $v_i$ has some neighbors outside those cliques, otherwise it would've become part of them.

We check that $W_i \cap \bigcup_{j>i} W_j$ is a clique. Because we remove cliques until nothing is left, $\bigcup_{j>i} W_j$ is just the edge set of the graph $G_{i+1}$. But $W_i \cap E(G_{i+1})$ is a clique for the same reason that $W_1 \cap E(G_2)$ is a clique, as above.

Another, possibly simpler way to construct the simplicial decomposition: start with the simplicial order, and let $W_i$ be the clique of $v_i$ and all its neighbors in $\{v_{i+1}, \dots, v_n\}$. This is almost the set of cliques we want, except possibly some are not maximal. But if they're not maximal, then it turns out that they're just subcliques of previous cliques, and we can simply delete them.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.