Some problems in the enumeration of labelled graphs
Some problems in the enumeration of labelled graphs
复制标题
标记图枚举中的一些问题
DOI：
10.1017/s0004972700011436
复制
发表时间：
1980
影响因子：
0.7
通讯作者：
N. Wormald
中科院分区：
文献类型：
--
作者：
N. Wormald
提出了一种对标记三连通图进行计数的方法。枚举是通过采用 3 连通图的新特征来完成的，该特征基于对从 3 连通图中删除一条线时可能产生的图的检查。相同的一般原理首先应用于计算连通图和 2 连通标记图。在所有这三种情况下，有必要跟踪点和线的数量。提供数值结果，显示连接、2 连接和 3 连接标记图的数量，其中 p 点最多为 20 。
A method of counting labelled 3-connected graphs is presented. The enumeration is accomplished by employing a new characterisation of 3-connected graphs, based on an examination of the graphs which may result when a line is removed from a 3-connected graph. The same general principle is first applied to counting connected and 2-connected labelled graphs. In all three cases, it is necessary to keep track of both the numbers of points and of lines. Numerical results are supplied, showing the numbers of connected, 2-connected and 3-connected labelled graphs with p points for p up to 20 .