CAJ | 학술논문

设I是图G的一个含有k个点的独立集(简称k独立集).如果I不是G的其它任何独立集的真子集，则称I为G的一个极大独立集.G中所含的极大k独立集的个数记为m(gl，G).设gk是图G的任一个k独立集，如果存在{v1，v2，…，vi} V(G)－gk，i≥1，使得(1)对任意j∈{1，2，…，i}，gk+{vj}的都是G的(k+1)-独立集；(2)对任意u∈V(G)－gk－{v1，v2，…vi}，gk+{u}的都不是G的独立集；则称gk为G的一个i爪k独立集，G所含的i爪k独立集的个数记为mi(gk，G).该文证明了对简单图G，mi(gk，G)和m(gk，G)都是可重构的.另外，用同样的方法可以证明G中的极大k团的个数及i爪k团的个数也是可重构的.
설I시도G적일개함유k개점적독립집(간칭k독립집).여과I불시G적기타임하독립집적진자집，칙칭I위G적일개겁대독립집.G중소함적겁대k독립집적개수기위m(gl，G).설gk시도G적임일개k독립집，여과존재{v1，v2，…，vi} V(G)－gk，i≥1，사득(1)대임의j∈{1，2，…，i}，gk+{vj}적도시G적(k+1)-독립집；(2)대임의u∈V(G)－gk－{v1，v2，…vi}，gk+{u}적도불시G적독립집；칙칭gk위G적일개i조k독립집，G소함적i조k독립집적개수기위mi(gk，G).해문증명료대간단도G，mi(gk，G)화m(gk，G)도시가중구적.령외，용동양적방법가이증명G중적겁대k단적개수급i조k단적개수야시가중구적.
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 k-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 ani-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(gk,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 G are also reconstructible.