论简单图所含k阶i爪独立集个数的可重构性

The Number of i-claw k-independent Sets of a Simple Graph is Reconstructible

设Ｉ是图Ｇ的一个含有ｋ个点的独立集（简称ｋ独立集）．如果Ｉ不是Ｇ的其它任何独立集的真子集，则称Ｉ为Ｇ的一个极大独立集．Ｇ中所含的极大ｋ独立集的个数记为ｍ（ｇｋ，Ｇ）．设ｇｋ是图Ｇ的任一个ｋ独立集，如果存在（ｖ１，ｖ２…ｖｉ｝Ｖ（Ｇ）－ｇｋ，ｉ≥１，使得（１）对任意ｊ∈｛１，２，…，ｉ｝，ｇｋ＋｛ｖｉ｝的都是Ｇ的（ｋ＋１）－独立集；（２）对任意的都不是Ｇ的独立集，则称ｇｋ为Ｇ的一个ｉ爪ｋ独立集，Ｇ所含的ｉ爪ｋ独立集的个数记为ｍｉ（ｇｋ，Ｇ）．该文证明了对简单图Ｇ，ｍ１（ｇｋ，Ｇ）和ｍ（ｇｋ，Ｇ）都是可重构的．另外，用同样的方法可以证明Ｇ中的极大ｋ团的个数及ｉ爪ｋ团的个数也是可重构的．

Let I be a k-independent set of graph G (i. e, an independent set of G which contains k vertices) . If I is not a proper subset of any other independent set of G, then I is called a maximal k-independent set of G. The number of maximal h-independent sets of G is denoted by m(gk,G). Let gk be a k-independent set of G. If there exists (v1,v2, vi)V(G)-gk,I≥1,such that (1) For any j∈{1,2,…i},gk+{vj} is a (k+1)-independent set of G, (2) For any u∈V(G)-gk-{v1,v2,vi},gk+{u} is not an independent set of G, then gk is called an i-claw k-independent set of G. Let mi(gk,G) denotes the number of i-claw k-independent sets of G. In this paper, it is proved that both mi(gi,G) and m(gk, G) are reconstructible for simple graphs. Similarly, both the number of maximal k-cliques in G and the number of i-claw k-cliques in C are also reconstructible.