论文标题
计数图形的连接分区
Counting Connected Partitions of Graphs
论文作者
论文摘要
由Gy \ H Ori和Lovász定理的激励，我们考虑了以下问题。对于$ n $顶点和$ m $的连接图$ g $，确定数字$ p（g，k）$的阳性整数解决方案$ \ sum_ {i = 1}^k m_i = m $，使每个$ m_i $都由连接的$ h_i $ g $ g $ g $ m_i $ edges实现，例如$ \ cup_ {i = 1}^ke（h_i）= e（g）$。我们还考虑了顶点分区类似物。 我们证明$ p（g，k）$上的各种下限是$ g $中的数字$ n $顶点的函数，这是$ g $的平均度$ d $ $ g $的函数，也是$ \ mathrm {cmc} _r（cmcc} _r（g）$ r $ r $ - r $ - r $ - r $ - r $ - r $ - r $ - r $ - r $ - r $ - $ r $ - 分机连接的最大值$ g $。这三个下限紧密至乘法常数。 我们还证明，$ \ sum_ {i = 1}^kn_i = n $的数字$π（g，k）$ thus $ k $ - tuples，可以通过顶点分区实现，这些分区可将其实现为$ k $连接的各个尺寸的部分$ n_1，n_2，n_2，n_2，n_k dots，n_k $，n_k $，n_k $，n_k $，$ ch^^^^^^^^^^^^^^{d^^{d^^{d^）
Motivated by the theorem of Gy\H ori and Lovász, we consider the following problem. For a connected graph $G$ on $n$ vertices and $m$ edges determine the number $P(G,k)$ of unordered solutions of positive integers $\sum_{i=1}^k m_i = m$ such that every $m_i$ is realized by a connected subgraph $H_i$ of $G$ with $m_i$ edges such that $\cup_{i=1}^kE(H_i)=E(G)$. We also consider the vertex-partition analogue. We prove various lower bounds on $P(G,k)$ as a function of the number $n$ of vertices in $G$, as a function of the average degree $d$ of $G$, and also as the size $\mathrm{CMC}_r(G)$ of $r$-partite connected maximum cuts of $G$. Those three lower bounds are tight up to a multiplicative constant. We also prove that the number $π(G,k)$ of unordered $k$-tuples with $\sum_{i=1}^kn_i=n$, that are realizable by vertex partitions into $k$ connected parts of respective sizes $n_1,n_2,\dots,n_k$, is $Ω(d^{k-1})$.
