Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-16T16:37:20.358Z Has data issue: false hasContentIssue false

Counting Coloured Graphs. III

Published online by Cambridge University Press:  20 November 2018

E. M. Wright*
Affiliation:
University of Aberdeen, Aberdeen, Scotland
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In an earlier paper [4], we found an asymptotic expansion for Mn = Mn(k), the number of coloured graphs on n labelled nodes, when n is large. Such a graph is a set of n distinguishable objects called nodes, and a set of “edges”, that is, undirected pairs of nodes. The nodes are mapped onto k colours. Every pair of nodes of different colours may or may not be joined by an edge, but no edge can join a pair of nodes of the same colour.

We write mn for the number of these graphs which are connected, Fn for the number which use all k colours (i.e., at least one node in each graph is mapped onto each of the k colours), and fn for the number of connected graphs which use all k colours.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1972