Keith Briggs

This page was last modified 2024-01-21  

.
.


home 
·publications 
·thesis 
·talks 
·meetings 
·records 
·maths notes « 
·software 
·languages 
·music 
·travel 
·cv 
·memberships 
·students 
·maps 
·place-names 
·people 
·photos 
·links 
·ex libris 
·site map 


.

Combinatorial graph theory

Introduction

This page collects together some data from my own computations, enumerating various types of graphs.

number of graphs on n nodes with edge chromatic number k

 k  | n=  1  2  3  4   5   6    7     8       9       10
--------------------------------------------------------
 0  |     1  1  1  1   1   1    1     1       1        1
 1  |     0  1  1  2   2   3    3     4       4        5
 2  |     0  0  1  3   5  10   15    26      37       58
 3  |     0  0  1  5  14  46  123   375    1061     3331
 4  |     0  0  0  0  10  58  347  2130   14039   103927
 5  |     0  0  0  0   2  38  392  4895   68696  1140623
 6  |     0  0  0  0   0   0  159  3855  113774  3953535
 7  |     0  0  0  0   0   0    4  1060   64669  4607132
 8  |     0  0  0  0   0   0    0     0   12378  1921822
 9  |     0  0  0  0   0   0    0     0       9   274734
10  |     0  0  0  0   0   0    0     0       0        0

number of connected graphs on n nodes with edge chromatic number k

 k  | n=  1  2  3  4   5   6    7     8       9       10
--------------------------------------------------------
 0  |     1  0  0  0   0   0    0     0       0        0
 1  |     0  1  0  0   0   0    0     0       0        0
 2  |     0  0  1  2   1   2    1     2       1        2
 3  |     0  0  1  4   8  26   58   185     500     1677
 4  |     0  0  0  0  10  48  279  1715   11464    87114
 5  |     0  0  0  0   2  36  352  4463   63363  1066463
 6  |     0  0  0  0   0   0  159  3696  109760  3835747
 7  |     0  0  0  0   0   0    4  1056   63605  4541399
 8  |     0  0  0  0   0   0    0     0   12378  1909444
 9  |     0  0  0  0   0   0    0     0       9   274725
10  |     0  0  0  0   0   0    0     0       0        0

number of graphs with specified clique and chromatic number

The following data was computed with my own codes for clique and chromatic number, together with nauty. Some of them extend sequences in the OEIS, in which case the A-number is given; others were new sequences before several were added to OEIS in February 2007.

number of graphs on n nodes with chromatic number k

n =  1   2   3   4    5    6     7      8        9       10 
k ----------------------------------------------------------
2    0   1   2   6   12   34    87    302     1118     5478   A076278
3    0   0   1   3   16   84   579   5721    87381  2104349   A076279
4    0   0   0   1    4   31   318   5366   155291  7855628   A076280
5    0   0   0   0    1    5    52    867    28722  1919895   A076281
6    0   0   0   0    0    1     6     81     2028   115391   A076282
7    0   0   0   0    0    0     1      7      118     4251
8    0   0   0   0    0    0     0      1        8      165
9    0   0   0   0    0    0     0      0        1        9
10   0   0   0   0    0    0     0      0        0        1
11   0   0   0   0    0    0     0      0        0        0
number of graphs on n nodes with clique number k

n =  1   2   3   4    5    6     7      8        9       10 
k ----------------------------------------------------------
2    0   1   2   6   13   37   106    409     1896    12171  A052450
3    0   0   1   3   15   82   578   6021   101267  2882460  A052451
4    0   0   0   1   4    30   301   4985   142276  7269487  A052452
5    0   0   0   0   1    5     51    842    27107  1724440  A077392 
6    0   0   0   0   0    1      6     80     1995   112225  A077393
7    0   0   0   0   0    0      1      7      117     4210  A077394
8    0   0   0   0   0    0      0      1        8      164 
9    0   0   0   0   0    0      0      0        1        9
10   0   0   0   0   0    0      0      0        0        1 
number of connected graphs on n nodes with chromatic number k

The first row is the same as the number of connected bipartite graphs on n nodes.

 n=   1   2   3   4    5    6     7      8        9        10
 k ------------------------------------------------------------
 2|   0   1   1   3    5   17    44    182      730      4032  A005142
 3|   0   0   1   2   12   64   475   5036    80947   2010328
 4|   0   0   0   1    3   26   282   5009   149551   7694428
 5|   0   0   0   0    1    4    46    809    27794   1890221
 6|   0   0   0   0    0    1     5     74     1940    113272
 7|   0   0   0   0    0    0     1      6      110      4125
 8|   0   0   0   0    0    0     0      1        7       156
 9|   0   0   0   0    0    0     0      0        1         8
10|   0   0   0   0    0    0     0      0        0         1
number of connected triangle-free graphs on n nodes with chromatic number k

The first row is the same as the number of connected bipartite graphs on n nodes.

 n=   1   2   3   4   5    6    7     8     9     10      11       12         13          14
 k -----------------------------------------------------------------------------------------
 2|   0   1   1   3   5   17   44   182   730   4032   25598   212780    2241730    31193324  A005142
 3|   0   0   0   0   1    2   15    85   650   5800   65243   931258   17182237   414512599
 4|   0   0   0   0   0    0    0     0     0      0       1       23       1085       75127
number of connected graphs on n nodes with clique number k

The first row is the same as the number of connected triangle-free graphs on n unlabeled nodes.

 n=   1   2   3   4    5    6     7      8        9        10
 k ------------------------------------------------------------
 2|   0   1   1   3    6   19    59    267     1380      9832   A024607
 3|   0   0   1   2   11   63   477   5339    94535   2774240
 4|   0   0   0   1    3   25   266   4646   136935   7121703
 5|   0   0   0   0    1    4    45    785    26205   1696407
 6|   0   0   0   0    0    1     5     73     1908    110140
 7|   0   0   0   0    0    0     1      6      109      4085
 8|   0   0   0   0    0    0     0      1        7       155
 9|   0   0   0   0    0    0     0      0        1         8
10|   0   0   0   0    0    0     0      0        0         1
number of biconnected graphs on n nodes with chromatic number k

 n=   1  2   3   4   5    6     7      8        9        10  
 k --------------------------------------------------------- 
 2|   0  0   0   1   1    5     8     42      146       956  
 3|   0  0   1   1   6   30   232   2762    50814   1420183 
 4|   0  0   0   1   2   17   189   3627   118114   6530233 
 5|   0  0   0   0   1    3    34    627    23262   1686975 
 6|   0  0   0   0   0    1     4     59     1631    101409 
 7|   0  0   0   0   0    0     1      5       92      3643 
 8|   0  0   0   0   0    0     0      1        6       135 
 9|   0  0   0   0   0    0     0      0        1         7 
10|   0  0   0   0   0    0     0      0        0         1 
number of biconnected triangle-free graphs on n nodes with chromatic number k

 n=   1  2  3   4   5   6   7    8     9     10      11       12        13          14
 k --------------------------------------------------------------------------------
 2|   0  0  0   1   1   5   8   42   146    956    6643    65921    818448    13442572
 3|   0  0  0   0   1   1   8   36   269   2418   29216   458445   9373692   249530113
number of connected 4-cycle-free graphs on n nodes with clique number k

 n=   1   2   3   4   5    6    7     8     9     10      11       12       13        14
 k ---------------------------------------------------------------------------------------
 2|   0   1   1   2   4    8   18    47   137    464    1793     8167    43645    275480
 3|   0   0   1   1   4   11   39   139   603   2925   16709   112054   888615   8321364

tables of numbers of unlabelled (US: unlabeled) graphs

This sequence is A000088 in OEIS. The previously best available data was to 68 nodes: Klas Markström's data. I have now reached 140 nodes by a sum-over-partitions method. For details of the method see W. Oberschelp, Math. Annalen, 174, 53-78.

The following file counts graphs by number of nodes only: oberschelp-gmp-02.500. The columns are:

1: n: number of nodes
2: np: number of partitions p(n) of n
3: ng: number g(n) of unlabelled graphs on n nodes
5: nc: number c(n) of connected unlabelled graphs on n nodes
7: log(1-fc): log(1-c(n)/g(n)). The fraction connected tends to 1
8: sqrtlogng: sqrt(log(g(n))). This is a function of the growth rate
9: log(ng/asymp-1): log(g(n)/(2^choose(n,2)/n!)-1). This compares with the asymptotic number

Here are plots of log(1-c(n)/g(n)) and log(g(n)/(2^choose(n,2)/n!)-1), to show the rate of approach to minus infinity of these quantities.

asymptotics of numbers of unlabelled graphs

I have improved the formula of Harary & Palmer (eq. 9.1.25, page 199) to include all terms up to k=11. The displayed equation gives the asymptotic expansion of g(n)/f(n), where f(n) is 2^{n(n-1)/2}/n!. The underline indicates a falling factorial.

counts of numbers of unlabelled graphs by edges

The following files count graphs by number of nodes and number of edges. The columns are:
1: number of nodes
2: number of edges
3: number of connected unlabelled graphs
4: total number of unlabelled graphs
5: fraction of connected graphs (column3/column4)

These were computed using this maple program by Brendan McKay, from the website of Gordon Royle.

diagrams of graphs

These are pdfs: with acrobat reader, zoom in with ctrl+.

The topologies were computed using the nauty program by Brendan McKay and the layouts created with graphviz. I wrote python programs to interface these and produce the pdfs.

plots of graph counts

tables of numbers of labelled graphs

I have data available for up to 2000 nodes, and excess up to 8.

labelled planar graphs

I have computed the number of labelled planar graphs up to 42 nodes, using a recurrence of Clemens Groepl:

data

useful external links

This website uses no cookies. This page was last modified 2024-01-21 10:57 by Keith Briggs private email address.