摘要
一、概念和记号 最近,Yousef Alavi等人在文献[*]中给出了图的升分解概念:已知图G,存在自然数n,G的边数q满足( )≤q≤( )。如果G能分解为子图G_1,G_2,…,G_n的并,使得G_i与G_(i+1)的一个真子图同构(1≤i≤n=1),G_i不含孤立点,则称这个分解为图G的一个升分解。
Y. Alavi has recently defined a new subgraph decomposition in paper, called“Ascending Subgraph Decomposition” . He also posed a conjecture. Let n≥2 be anatural number and G be a union of isolated stars s1s2,…,sk,where si has ai edges,n≤ai≤2n-2, andThen G has an ascending stars decomposition. Itis proved in this paper that the conjecture is true if one of the following conditionsis satisfied.1. n≤ai≤ai+1(i=1,2, … ,k-2), and ak-1<(n-k+2),ak≥n;2. at least k-1 of {ai,a2,…,ak} has are equal each other;3. ai≤ai+1,ai+1-ai =m, where m≤2 and 1≤i≤k-1
出处
《数学进展》
CSCD
北大核心
1991年第2期240-246,共7页
Advances in Mathematics（China）
