摘要
在文献[2]中作者定义了图的一种新分解-升分解(Ascending SubgraphDecomposition简记为ASD),并提出了一个猜想:任意有正数条边的图都可以升分解.本文主要证明了二部图Km1m2-Hm2(m1≥m2)可以升分解,其中Hm2是至多含m2条边的Km1m2的子图.
In [2], the authors defined a new decomposition of graph-Ascending Subgraph Decom-position (ASD), and proposed the following conjecture: every graph of positive size has an ASD. In this paper, we prove that bipartite graph Km1,m2-Hm2(m1≥m2) has an ASD, in which Hm2 is a subgraph of Km1,m2 with not more than m2 edges.
出处
《应用数学与计算数学学报》
2003年第2期85-90,共6页
Communication on Applied Mathematics and Computation
关键词
升分解
完全二部图
二部图
匹配
ascending subgraph decomposition, complete bipartite graph, bipartite graph, matchings
