摘要
Ｙｏｕｓｅｆ．Ａｌａｖｉ等人在文献［１］中定义了一种新分解（Ａｓｃｅｎｄｉｎｇ Ｓｕｂｇｒａｐｈ Ｄｅｃｏｍｐｏｓｉ－ ｔｉｏｎ），即“升分解”，并且猜想：任意有正整数条边的图都可以升分解．本文证明了下面两个结 论： １．Ｋｎ－Ｈ２ｎ＋１可以升分解，其中Ｈ２ｎ＋１为含有２ｎ＋１条边的Ｋｎ的子图； ２．Ｋｎ－Ｈ２ｎ＋２可以升分解，其中Ｈ２ｎ＋２为含有２ｎ＋２条边的Ｋｎ的子图．
A conjecture concerning the ascending subgraph decomposition posed by Y. Alavi et. al in [1] is as follows: Every graph of positive size has an ascending subgraph decomposition. This note prove the following two results. 1. Kn - H2n+1 (n≥ 8) can be ascending subgraph decomposition into K1,1 ,K1,2,...,K1,n-5,Gn-4; 2. Kn - H2n+1 (n≥ 10) can be ascending subgraph decomposition into K1,1,K1,2,..., K1,n-5,Gn-4.
基金
东省自然科学基金资助项目(Y97A10015)
关键词
升分解
对集
完全图
子图
简单图
ascending subgraph decomposition
conjecture.
