# zbMATH — the first resource for mathematics

The number of $$i$$-claw $$k$$-independent sets of a simple graphs is reconstructible. (Chinese. English summary) Zbl 0986.05077
An independent set $$g_k$$ of a graph $$G(V,E)$$, which contains $$k$$ vertices, is called a $$k$$-independent set of $$G(V,E)$$. A $$k$$-independent set is said to be maximal if it is not a proper subset of any other independent set of $$G(V,E)$$. If there exists $$\{v_1,v_2,\dots, v_i\}\subset V- g_k$$, $$i\geq 1$$, such that (1) for any $$j\in \{1,2,\dots, i\}$$, $$g_k+\{v_j\}$$ is a $$(k+1)$$-independent set, and (2) for any $$u\in V- g_k- \{v_1,v_2,\dots, v_i\}$$, $$g_k+ \{u\}$$ is not an independent set of $$G(V,E)$$, $$g_k$$ is called an $$i$$-claw $$k$$-independent set. The paper shows that both the number of $$i$$-claw $$k$$-independent sets and the number of maximal $$k$$-independent sets of $$G(V,E)$$ are reconstructible for simple graphs. Likewise, both the number of $$i$$-claw $$k$$-cliques and the number of maximal $$k$$-cliques in $$G(V,E)$$ are also reconstructible.
##### MSC:
 05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
##### Keywords:
reconstruction; independent set