论文标题
将完整的两分图分解为跨越半缘因子
Factorisation of the complete bipartite graph into spanning semiregular factors
论文作者
论文摘要
在几种情况下，我们将完整的两分图的分解为跨越半图形图，包括当所有因素的程度以外的一个或两个都小时。可以看到所得的渐近行为以优雅的方式概括了半毛图的数量。与顶点数量相比，当因素消失时，这使我们猜想了一般公式。作为推论，我们发现在某些情况下，将随机半毛线二分图的边缘划分为跨越半图的边缘的平均数量。我们对一个案例的证明使用一个开关参数来发现一组足够稀疏的半毛线二分组图是在随机标记时是边缘 - 偶会的概率。
We enumerate factorisations of the complete bipartite graph into spanning semiregular graphs in several cases, including when the degrees of all the factors except one or two are small. The resulting asymptotic behaviour is seen to generalise the number of semiregular graphs in an elegant way. This leads us to conjecture a general formula when the number of factors is vanishing compared to the number of vertices. As a corollary, we find the average number of ways to partition the edges of a random semiregular bipartite graph into spanning semiregular subgraphs in several cases. Our proof of one case uses a switching argument to find the probability that a set of sufficiently sparse semiregular bipartite graphs are edge-disjoint when randomly labelled.
