<p>The best way to do it, if you want to generate billions of graphs is to read up on enumeration algorithms such as:</p>

<p>[Yasuko Matsui, Ryuhei Uehara and Takeaki Uno, Enumeration of Perfect Sequences of Chordal Graph (2008)]</p>

<p>However for many this may be more than what is needed.
An easier algorithm is:</p>

<ol>
<li>Enumerate all chordal graphs on n-1 vertices.</li>
<li>For each chordal graph G on n-1 vertices and each clique C in G.
Create a graph G' by adding a vertex v with neighbours C.</li>
<li>If G' has not already been found, add G to the list of chordal graphs on n vertices.</li>
</ol>

<p>By this algorithm you should be able to generate the chordal graphs on at most 11 vertices which means over a million graphs.</p>

CC BY-SA 3.0
2015-01-31T06:23:24.227Z
Why not more than 11 vertices? What happens if we use this algorithm for 20 vertices?
Rahul Yadav
CC BY-SA 3.0
2015-01-31T10:48:58.277Z
You can of course use it for 20 vertices, it just takes longer time. I estimated that 11 vertices would finish within reasonable time, the number of operations needed is something like n! So 20 vertices takes 60 billion times longer so that would be a million years.
Martin Vatshelle
CC BY-SA 3.0
2015-02-01T13:21:33.937Z
Sure! great thanks.
So is there any formula or pattern/equation by which we can get the number quickly rather than the brute force approach?
Rahul Yadav
CC BY-SA 3.0
2015-02-01T18:08:20.910Z
The OEIS contains the numbers up to 12 vertices, so whoever computed these numbers didn't use an algorithm that worked better than the one given in this answer.
Peter Shor 
CC BY-SA 3.0
2015-01-29T22:34:45.717Z
2015-01-29T22:34:45.717Z
Martin Vatshelle
<p>A chordal Graph is a connected graph which contains no chord-less cycle of size greater than three.
They are also called as Triangulated graphs. </p>

<p>All Paths are Chordal Graphs (No cycles).</p>

<p>All Trees are chordal Graphs (No cycles).</p>

<p>All cliques are chordal graphs. </p>

<p>A Path contains the minimum no of edges and a clique contains the maximum number of edges of a given n vertices chordal graph</p>

<p><a href="http://en.wikipedia.org/wiki/Chordal_graph" rel="nofollow">Wiki Link for more explanation of chordal graphs </a> </p>

<p>So for a fixed number 'n', what is the algorithm to find all the possible chordal graphs of n vertices? </p>

<p>For example: </p>

<ul>
<li>n= 2, Answer = 1 chordal graph. </li>
<li>n= 3, Answer = 2 chordal graphs, </li>
<li>n= 4, Answer = 5 chordal graphs, </li>
<li>n= 5, Answer = 15 chordal graphs.</li>
</ul>

<p>The above are determined by drawing all possible examples. Any algorithm? </p>

CC BY-SA 3.0
2015-01-29T20:38:40.557Z
What requirements do you have? What do you intend to do with them? Do you just need the number, or explicit graphs? One algorithm generates all simple graphs on n vertices and runs a recognition algorithm. Check OEIS for the numbers.
Juho
CC BY-SA 3.0
2015-01-29T22:04:11.173Z
Do you want to find these graphs or just know the number of such graphs?
Here you can find the first few numbers https://oeis.org/A048192
Martin Vatshelle
CC BY-SA 3.0
2015-01-29T22:49:56.577Z
As others mentioned what's your question exactly. If you really want to generate them all then what's the upperbound for n? Number of them is superexponential so you should have a reasonable n (and a good reason). Also if you are interested just in number of them is approximation suitable for you or just the exact number?
Saeed
CC BY-SA 3.0
2015-01-31T06:04:58.273Z
@Martin Yes, I needed the exact number. I've seen your link and yes it's contains only the output I need! I need the algorithm!
Rahul Yadav
<cc.complexity-theory><graph-theory><graph-algorithms>
What is the Algorithm to find all the possible chordal graphs which can be formed by a given 'n' number of vertices
Rahul Yadav
# What is the Algorithm to find all the possible chordal graphs which can be formed by a given 'n' number of vertices

(Asked by: username_0 on 2015-01-29)

A chordal Graph is a connected graph which contains no chord-less cycle of size greater than three.
They are also called as Triangulated graphs.

All Paths are Chordal Graphs (No cycles).

All Trees are chordal Graphs (No cycles).

All cliques are chordal graphs.

A Path contains the minimum no of edges and a clique contains the maximum number of edges of a given n vertices chordal graph

[Wiki Link for more explanation of chordal graphs](http://en.wikipedia.org/wiki/Chordal_graph)

So for a fixed number 'n', what is the algorithm to find all the possible chordal graphs of n vertices?

For example:

* n= 2, Answer = 1 chordal graph.
* n= 3, Answer = 2 chordal graphs,
* n= 4, Answer = 5 chordal graphs,
* n= 5, Answer = 15 chordal graphs.

The above are determined by drawing all possible examples. Any algorithm?

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms
> **Comments:**
> **username_1**: What requirements do you have? What do you intend to do with them? Do you just need the number, or explicit graphs? One algorithm generates all simple graphs on n vertices and runs a recognition algorithm. Check OEIS for the numbers.  
> **username_2**: Do you want to find these graphs or just know the number of such graphs? Here you can find the first few numbers https://oeis.org/A048192  
> **username_3**: As others mentioned what's your question exactly. If you really want to generate them all then what's the upperbound for n? Number of them is superexponential so you should have a reasonable n (and a good reason). Also if you are interested just in number of them is approximation suitable for you or just the exact number?  
> **username_0**: @Martin Yes, I needed the exact number. I've seen your link and yes it's contains only the output I need! I need the algorithm!  

---

## 1 answers

### Answer by username_2 on 2015-01-29. Score: 2 | Accepted answer

The best way to do it, if you want to generate billions of graphs is to read up on enumeration algorithms such as:

[Yasuko Matsui, Ryuhei Uehara and Takeaki Uno, Enumeration of Perfect Sequences of Chordal Graph (2008)]

However for many this may be more than what is needed.
An easier algorithm is:

1. Enumerate all chordal graphs on n-1 vertices.
2. For each chordal graph G on n-1 vertices and each clique C in G.
   Create a graph G' by adding a vertex v with neighbours C.
3. If G' has not already been found, add G to the list of chordal graphs on n vertices.

By this algorithm you should be able to generate the chordal graphs on at most 11 vertices which means over a million graphs.

> **Comments:**
> **username_0**: Why not more than 11 vertices? What happens if we use this algorithm for 20 vertices?  
> **username_2**: You can of course use it for 20 vertices, it just takes longer time. I estimated that 11 vertices would finish within reasonable time, the number of operations needed is something like n! So 20 vertices takes 60 billion times longer so that would be a million years.  
> **username_0**: Sure! great thanks. So is there any formula or pattern/equation by which we can get the number quickly rather than the brute force approach?  
> **username_4**: The OEIS contains the numbers up to 12 vertices, so whoever computed these numbers didn't use an algorithm that worked better than the one given in this answer.  

---

