0
$\begingroup$

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

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Juho
    Jan 29, 2015 at 20:38
  • 1
    $\begingroup$ Do you want to find these graphs or just know the number of such graphs? Here you can find the first few numbers oeis.org/A048192 $\endgroup$
    – Martin Vatshelle
    Jan 29, 2015 at 22:04
  • $\begingroup$ 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? $\endgroup$
    – Saeed
    Jan 29, 2015 at 22:49
  • $\begingroup$ @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! $\endgroup$
    – Rahul Yadav
    Jan 31, 2015 at 6:04

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Why not more than 11 vertices? What happens if we use this algorithm for 20 vertices? $\endgroup$
    – Rahul Yadav
    Jan 31, 2015 at 6:23
  • $\begingroup$ 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. $\endgroup$
    – Martin Vatshelle
    Jan 31, 2015 at 10:48
  • $\begingroup$ 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? $\endgroup$
    – Rahul Yadav
    Feb 1, 2015 at 13:21
  • $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Feb 1, 2015 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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