Tata Institute of Fundamental Research
An Introduction to Chordal Graphs And Clique Trees
STCS Student Seminar
Speaker:
Vidya Sagar Sharma
Organiser:
Sayantan Chakraborty
Date:
Saturday, 30 Jan 2021, 17:15 to 18:15
Venue:
(Scan to add to calendar)
Abstract:
An undirected graph is chordal if every cycle of length greater than three has a chord: namely, an edge connecting two nonconsecutive vertices on the cycle. A clique of a graph $G$ is any maximal set of vertices that is complete in $G$. Let $G$ be a chordal graph and $K_G = \{ K_1, K_2, ..., K_m \}$ denotes the set containing the cliques of $G$, then a tree with vertex set $K_G$ is said to be a clique tree of the chordal graph $G$ if it follows the clique intersection property: For every pair of distinct cliques $K,K' \in K_G$, the set $K \cap K'$ is contained in every clique on the path connecting $K$ and $K'$ in the tree.
In this talk, we will see a few properties of the chordal graphs and the clique trees of the chordal graphs.
Reference: link.springer.com/content/pdf/10.1007%2F978-1-4613-8369-7_1.pdf
Zoom Link : https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09
| Speaker: | Vidya Sagar Sharma |
| Organiser: | Sayantan Chakraborty |
| Date: | Saturday, 30 Jan 2021, 17:15 to 18:15 |
| Venue: |
(Scan to add to calendar)
Abstract:
An undirected graph is chordal if every cycle of length greater than three has a chord: namely, an edge connecting two nonconsecutive vertices on the cycle. A clique of a graph $G$ is any maximal set of vertices that is complete in $G$. Let $G$ be a chordal graph and $K_G = \{ K_1, K_2, ..., K_m \}$ denotes the set containing the cliques of $G$, then a tree with vertex set $K_G$ is said to be a clique tree of the chordal graph $G$ if it follows the clique intersection property: For every pair of distinct cliques $K,K' \in K_G$, the set $K \cap K'$ is contained in every clique on the path connecting $K$ and $K'$ in the tree.
In this talk, we will see a few properties of the chordal graphs and the clique trees of the chordal graphs.
Reference: link.springer.com/content/pdf/10.1007%2F978-1-4613-8369-7_1.pdf
Zoom Link : https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09
In this talk, we will see a few properties of the chordal graphs and the clique trees of the chordal graphs.
Reference: link.springer.com/content/pdf/10.1007%2F978-1-4613-8369-7_1.pdf
Zoom Link : https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09