Counting connected sets and connected partitions of a graph
Counting connected sets and connected partitions of a graph
复制标题
计算图的连通集和连通分区
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
A. Vince
中科院分区：
文献类型：
--
作者：
A. Vince
本文研究了点标图的两个相关计数问题。给出了这样一个图G，我们研究了该顶点集的连通子集的个数C(G)和该顶点集的连通划分的个数P(G)。我们所说的连通是指导出子图是连通的。数C(G)和P(G)可分别视为n元集合的子集个数和集合划分个数的(连通)图模拟。
This paper concerns two related enumeration problems on vertex labeled graphs. Given such a graph G, we investigate the number C(G) of connected subsets of the vertex set and the number P (G) of connected partitions of the vertex set. By connected we mean that the induced subgraphs are connected. The numbers C(G) and P (G) can be regarded as the (connected) graph analogs of the number of subsets and the number of set partitions, respectively, of an n-element set.