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.
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)