关于图的一种新分解

一、概念和记号 最近,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的一个升分解。     

关于图的一种新分解

Alavi等人在[1]中定义了图的一种新分解,即升分解,并提出猜想:     

On the Ascending Subgraph Decompositions Problem

Inthispaper,weconsideronlysimpleundirectedgraphsandfollowBondyandMurtyl7]forterminologyandnotationnotdefinedhere.Y.Alaviandothershavegiventhedefinitionoftheascendingsubgraphdecomposionin[1].LetGbeagraphofqedgessatisfy(" 1)5q<(" ,).ThenGissaidtohavean...     

几类可升分解的图

Ａｌａｖｉ等人在文献［１］中定义了图的一种新分解，即“升分解”，并且猜想：任意有正数条边的图都可升分解。本文证明了下面三类图可升分解，并得到了一些有意义的推论。１设Ｒｎ是一个至多含有ｎ个顶点和至多含有ｎ条边的图，Ｋｎ－Ｒｎ可升分解（ｎ≥５）；２对称图可升分解；３对称图Ｇ的混合积（Ｇ；ｋ）可升分解。     

关于图Kn-H2n+i(i=1,2)的升分解

Ｙｏｕｓｅｆ．Ａｌａｖｉ等人在文献［１］中定义了一种新分解（Ａｓｃｅｎｄｉｎｇ Ｓｕｂｇｒａｐｈ Ｄｅｃｏｍｐｏｓｉ－ ｔｉｏｎ），即“升分解”，并且猜想：任意有正整数条边的图都可以升分解．本文证明了下面两个结 论： １．Ｋ_n-H_2n+1可以升分解，其中Ｈ_2n+1为含有２ｎ＋１条边的Ｋ_n的子图； ２．Ｋ_n-H_2n+2可以升分解，其中Ｈ_2n+2为含有２ｎ＋     

Some graphs which have ascending subgraph decomposition

1.IntroductionIn[1],Alavietal.gavethefollowingdecompositionconjecture.Conjecture.LetGbeagraphwith("1')edges.ThentheedgesetofGcanbedecomposedintonsetsgeneratinggraphsGI,G2,'IG.suchthatIE(Gi)I=i(fori=1,2,',n)andGiisisomorphictoasubgraphofGi 1fori=1,2,'.)n--1.AgraphGthatcanbedecomposedasdescribedinConjecturewillbesaidtohaveanAscendingSubgraphDecomposition(AlsoabbreviatedasASD).ThesubgraphsGIIG2,',G.aresaidtobemembersofsuchadecomposition.Furthermore,ifeachGiisastar(matching,pat…     

关于图的升分解的Alavi猜想

Y.Alavi等人在1987年定义了图的一种新分解,即“升分解”(ascebding subgraph decomposition),并提出猜想:设自然数n≥2,G是由k个分离的星S_1,S_2,…,S_k构成的图,S_i含有a_i条边,n≤a_i≤2n-2,,则G可升分解为星的并。本文证明了当n=2k+i(i=0,1,2)时猜想成立。     

关于愉快图的Bodendiek猜想

In 1977, H. Bodendiek, H. Schumach and H. Wegner proposed the following conjecture.Conjecture. The graphs consisting of a cycle plus one edge joining two non-adjacent vertices are graceful.In this paper, we have proved the following result.It is Graceful Graph for any cycle cn to be added one edge joining two non-adjacent vertices so we have C_m′.     

关于P（n1,n2,...nm）和Dm,4的优美性

一个简单图G=(V,E)是k-优美的(k≥1的整数),如果存在一个1-1映射 f:V(G)→(0,1,…,|E| k-1)使得对所有的边e=wv∈E(G),由f~*(u,v)=|f(u)-f(v)|导出的映射 E(G)→{k,k 1,…,|E| k-1}是一个1-1对应。这个关于k-优美的概念是由Slater和Thuillier相互独立地提出来的。当k=1,就是我们通常研究的优美图。显然,k-优美图一定是1-优美图。反之不真。例如,三回路c_3是1-优美图,但对k>1,非k-优美。     

关于整数分拆的Alavi猜想的证明

Ｙ．Ａｌａｖｉ，Ｐ．Ｅｒｄｓ等人在［１］中提出猜想：设自然数α＿１，α＿２…α＿ｋ满足且，则可以划分成ｋ个互不相交子集Ｓ＿１，Ｓ＿２，···，Ｓ＿ｋ，满足．本文证明了这个猜想。