Acta mathematica scientia,Series A ›› 2001, Vol. 21 ›› Issue (2): 284-288.
• Articles • Previous Articles
XIE Li-Tong
Online:
Published:
Supported by:
国家教委博士点基金资助项目
Abstract:
设犐是图犌的一个含有犽个点的独立集(简称犽独立集).如果犐不是犌的其它任何独立集的真子集,则称犐为犌的一个极大独立集.犌中所含的极大犽独立集的个数记为犿(犵犽,犌).设犵犽是图犌的任一个犽独立集,如果存在{狏1,狏2,…,狏犻}犞(犌)-犵犽,犻≥1,使得(1)对任意犼∈ {1,2,…,犻},犵犽+{狏犼}的都是犌的(犽+1)独立集;(2)对任意狌∈犞(犌)-犵犽-{狏1,狏2,…,狏犻},犵犽+{狌}的都不是犌的独立集;则称犵犽为犌的一个犻爪犽独立集,犌所含的犻爪犽独立集的个数记为犿犻(犵犽,犌).该文证明了对简单图犌,犿犻(犵犽,犌)和犿(犵犽,犌)都是可重构的.另外,用同样的方法可以证明犌中的极大犽团的个数及犻爪犽团的个数也是可重构的.
Key words: 图, k阶i爪独立集, 重构, i爪k团
CLC Number:
XIE Li-Tong. The Number of i-claw k-independent Sets of a Simple Graph is Reconstructible[J].Acta mathematica scientia,Series A, 2001, 21(2): 284-288.
0 / / Recommend
Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks
URL: http://121.43.60.238/sxwlxbA/EN/
http://121.43.60.238/sxwlxbA/EN/Y2001/V21/I2/284
1 BondyJA,Murty,USR.Graphtheorywithapplications.MacmillanPressLtd.1976 2 Kocay W L.lectureNotesin Mathematics952.Springer,1982 3 TutteW T.AlltheKing'shorses.In:JABondyandUSR Murtyeds.GraphTheoryandRelatedTopics.AcademicPress,1979.15-33 4 BondyJA.A Reconstructor'sManual.Universityofwaterloo,1991 5 李慰萱译,F.哈拉里著.图论.上海科学技术出版社,1980 6 HararyF,NikolopoulosSD.Oncompletesystemsofinvariantsforsmallgraphs.IntJComputMath,1997,64:1-2,35-46
Cited