摘要
Ａｌａｖｉ等人在文献［１］（Ｃｏｎｇｅｒ．Ｎｕｍｅｒ．，１９８７，５８：７１４．）中定义了图的一种新分解，即“升分解”（ａｓｃｅｎｄｉｎｇｓｕｂｇｒａｐｈｄｅｃｏｍｐｏｓｉｔｉｏｎ），并且猜想：任意有正数条边的图都可升分解．本文证明了下面三类图可升分解，并得到了一些有意义的推论．１设Ｒｎ是一个至多含有ｎ个顶点和至多含有ｎ条边的图，Ｋｎ－Ｒｎ可升分解（ｎ５）；２对称图可升分解；３对称图Ｇ的混合积〈Ｇ；
Alavi has given the definition of the ascending subgraph decomposition(ASD), and conjectured that every graph of positive size has an ascending subgraph decomposition. In this paper, it is shown that three kinds of graphs have an ascending subgraph decomposition, and we obtained some good corollaries. (1) Let R n be any at most n edge graph with at most n vertices, then K n-R n has an ASD. (2) Let G be symmetric graph, then G has an ASD. (3) Let G be symmetrie graph, then the mixed product of graph of G〈G;k〉 has an ASD.
出处
《数学进展》
CSCD
北大核心
1997年第1期66-71,共6页
Advances in Mathematics（China）
基金
国家自然科学基金
关键词
升分解
对称图
混合积
图论
ascending subgraph decomposition
symmetric graph
the mixed product of graph
