Graph Catalogs

In this page, we provide some graph catalogs.

Interval graphs

The lists provide all nonisomorphic interval graphs of n vertices for n=1,2,...,12. The numbers of graphs are summarized as follows
The number of vertices 1 2 3 4 5 6 7 8 9 10 11 12 13 14
The number of interval graphs: LIST, OEIS:A005975 1 2 4 10 27 92 369 1807 10344 67659 491347 3894446
The number of connected interval graphs: LIST, OEIS:A005976 1 1 2 5 15 56 250 1328 8069 54962 410330 3317302
Each interval graph is represented in one line in a simple text format, e.g., 1 1 2 2 3 3 (independent set of three vertices), 1 2 1 3 2 3 (path of length 3), 1 2 3 3 2 1 (complete graph of size 3).

Permutation graphs

The lists provide all nonisomorphic permutation graphs of n vertices for each of n=1,2,...,6. The numbers of graphs are summarized as follows
The number of vertices 1 2 3 4 5 6 7 8
The number of permutation graphs 1 2 4 11 33 142 776 5699
The number of connected permutation graphs 1 1 2 6 20 99 600 4753
Each permutation graph represented in one line in a simple text format, e.g., 1 2 3 (independent set of three vertices), 2 3 1 (path of length 3), 3 2 1 (complete graph of size 3).

Connected Proper Interval graphs

The list provides all nonisomorphic proper interval graphs of n vertices for n=1,2,...,23. The numbers of graphs are summarized as follows
The number of vertices 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
The number of connected proper interval graphs: 1 1 2 4 10 26 76 232 750 2494 8524 29624 104468 372308 1338936 4850640 17685270 64834550 238843660(608M) 883677784(2216M) 3282152588(8136MB) 12233309868(31GB) 45741634536(115GB)
Each interval graph is represented in one line in a simple text format, e.g., [[[]]] (complete graph of size 3), [[][]] (path of length 3).

Histrory


Last modified: Fri Dec 24 20:14:43 JST 2010
by Ryuhei Uehara (uehara@jaist.ac.jp)
Valid HTML 4.0!