资源描述：
《针对变换图g的独立数》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第23卷第6期四川理工学院学报(自然科学版)Vol23No62010年12月JournalofSichuanUniversityofScience&Engineering(NaturalScienceEdition)Dec2010文章编号:16731549(2010)06063904*xy变换图G的独立数顾秀松,徐丹丹(解放军理工大学理学院,南京211101)摘要:变换图的概念由全图推广而来。文章在中图的补图M(G)的定义启发下,定义了四类变换*-+图,其中一个恰是M(G),并探讨了这些变换图的独立数。研究了变换图G的独立数与原图最大度*++*+-的关系,以及
2、G与G的独立数与原图边独立数的关系。关键词:变换图;独立集;独立数中图分类号:O1575文献标识码:A中相邻;x=-时当且仅当和在图G中不相邻。引言(iii)V(G),E(G),y=+时当且仅当和本文所讨论的图均为简单图。设G=(V(G),E在图G中关联;y=-时当且仅当和在图G中不关(G))是图,V(G)=n,记G的独立数为(G),联。*--IG(v)为G中与点v相关联的边的集合,(G)为G的由上述定义,得到4种变换图。其中G就是最大匹配的边数。其他未说明的术语及概念见文献M(G)。例如,GK3,它的四类变换图如图1。[1]。变换图的概念是由全图推
3、广而来。近年来,不少*xy1G的独立数学者陆续对包括全图在内的8类变换图的性质进行了[27]文献[8]证明了变换图G*--的独立数与原图最大研究,如连通性,直径,同构问题等等。图G的中图M(G)以及中图的补图M(G)也是被广泛研究的变换度的关系。本文则求出了其它3种图的独立数。[8]*--图[810]。中图M(G)以V(G)E(G)为其顶点集,两个定理1对任意图G,(G)=(G)+1。*-+顶点和在M(G)中相邻当且仅当和中至少有一定理2(1)对任意图G,(G)(G)个属于E(G),并且它们在G中相邻或相关联。M(G)以(G)+2。*-+V(G)E(
4、G)为顶点集,对任意的,V(G)(2)(G)=(G)+2当且仅当K3是G的真子E(G),和在M(G)中邻接的条件如下:(i),V图且(G)=2。*-+(3)(G)=(G)当且仅当(G)=n-1且G(G)。(ii),E(G),且它们在图G中不相邻。(iii)V(G),E(G),和在图G中不关联。不同构于K3、K4、K4-e及G0,其中G0如图2所示。*-+受M(G)定义的启发,可以定义下类变换图。证明(1)任取点vV(G),IG(v)是G的独*-+定义设G=(V(G),E(G))是简单图,x,y{+,立集。因为IG(v)=d(v)
5、,所以(G)(G)。*xy*-+*-+-}。变换图G以V(G)E(G)为其顶点集,对任意现设S是G的独立集。由G的定义知S至多含有*xy的,V(G)E(G),和在图G中邻接的条件V(G)中的一个点。如下:情况1SV(G)={v},设S={v,e1,e2,,(i),V(G)。em}。于是边e1,e2,,em在G中两两相邻。(ii),E(G),x=+时当且仅当和在图G情况11G[e1,e2,,em]是星图K1,m,则S=收稿日期:20101013基金项目:国家自然科学基金资助项目(70571087)作者简介:顾秀松(1980),女,
6、江苏南京人,讲师,硕士,主要从事图论方面的研究。640四川理工学院学报(自然科学版)2010年12月边e1,e2,e3及K3外一点u。于是,S={u,e1,e2,e3}是*-+*-+G的独立集,因此,(G)4。*-+假设S是G的最大独立集且S5。因为S至多含有V(G)中的一个点,所以S中至少含有E(G)中的4条边a1,a2,a3,a4。这4条边在G中两两相邻,因此G[a1,a2,a3,a4]为K1,4,与(G)=2矛盾。故*-+(G)=4=(G)+2。(3)先证必要性。假设(G)=rn-2,则*-+(G)=r。*-+设点v是G的最
7、大度点。由于IG(v)是G的独*-+立集,且IG(v)=dG(v)=r,故IG(v)是G的最大独立集。另一方面,V(G[IG(v)])=r+1n-1,故G中在G[IG(v)]外至少还存在一点u。由定义,{u}*-+*-+IG(v)是G的独立集,与IG(v)是G的最大独立集矛盾。因此(G)=n-1。*-+若G同构于K3,则(G)=3,而(G)=2,与*-+(G)=(G)矛盾。*-+若G同构于K4、K4-e及G0,则(G)=4,而(G)=3,矛盾。*-+再证充分性。
