Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

A graph $G$ is chordal if it is the intersection graph of subtrees of a tree $T$. In particular $T$ can be chosen such that each node of $T$ corresponds to a maximal clique of $G$ and the subtrees $T_v$ consist of precisely those maximal cliques in $G$ that contain $v$. $T$ is then called the clique tree of $G$.

Now my question is the following.

Is any tree can be represented as a clique tree of some chordal graph?

Any counter example or hint of proof is welcome.

share|improve this question

2 Answers 2

up vote 4 down vote accepted

Chordal graphs can be defined as intersection graph of subtrees of any tree. So the answer to your decision question is trivially YES. On the construction side, for each subtree $T_v$ of bags (it's convenient and conventional to call the nodes of the tree as bags), you'll have a unique new vertex $v$, which is put into all bags of the $T_v$.

share|improve this answer
    
Excuse me, but it's hard for me to understand your answer. Would you clarify how you construct a chordal graph from a tree? –  Yoshio Okamoto Mar 8 at 12:10

If I understood your question correctly, you want to know whether every tree $T$ is the clique tree of a chordal graph $G$. In this case, the answer is yes.

To see this, take the family of subtrees being the set of vertices and the set of edges of $T$.

To see that the vertices of $T$ correspond to the maximal cliques of $G$, notice that for each node $C$ of $T$ there is a subtree $T_v$ corresponding to it, hence $v$ is a simplicial vertex on $G$ and cannot be adjacent to any other vertex non-incident in $C$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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