On \(S_0\)-free forests with man independent sets (Q2811814)

In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. Equivalently, each edge in the graph has at most one endpoint in \(S\). The size of an independent set is the number of vertices it contains. Independent sets have also been called internally stable sets. The vertex independence number of a graph, often called simply ``the'' independence number, is the cardinality of the largest independent vertex set, i.e., the size of a maximum independent vertex set. The authors basically prove some results on \(m\) stars with \(m\)-edges, where an isolated vertex is involved. Usually the order plays a role for determining the possible bound for cardinality of independent sets. Here, an attempt is made in terms of size, basically the first ten largest numbers of independent sets among all \(S_0\) free forests of size \(m\). The discussion begins with the normal nomenclatures in graph theory such as neighborhood, closed neighborhood, odd-sized component, union, isomorphic graphs, vertex degree, tree, forest, leaf, etc. Some citations related to combinatorial chemistry is placed, topological methods in chemistry appear as another possible aspect in this facet. Some classes such as \(\mathcal F_{m,s}\), \(F( m,s)\), \(F( m,s)\), \(F^\prime(m,s)\) and \(f(m,s)\), \(f^\prime(m,s)\mathcal F_{m,s}\) are staged for the purpose connecting trees such as \(S_1\), \(S_2\), \(S_3\), \(S_4\) of sizes 1, 2, 3, 4, respectively. The only main result giving the first ten largest numbers of independent sets is based on some lemmas that lead to what is being expected. The lemmas are playing roles for the purpose. Some of them may be cited as: Let \(T\) be a tree of size \(m\geq 2\) and \(x\) a leaf of \(T\). Suppose that \(F=S_1\cup(T-x)\), then \(F\) is an \(S_0\)-free forest of size \(m\) having \(i(F)>i(T)\). And if \(F\) is an \(S_0\)-free forest of size \(m\geq 1\), then \(i(F)\leq 3^m\) with equality holding if and only if \(F=mS_1\), when the size of the tree is \(m\geq 4\) with a path \(P\) where \(V(P)=\{x_1,x_2,y\}\), and \(T-\{x_1,x_2\}\) is a tree, and \(F=S_2\cup(T-\{x_1,x_2\} )\), then \(F\) is an \((S_0,S_1)\)-free forest of size \(m\) having \(i(F)>i(T)\), for an \((S_0,S_1)\)-free forest of size \(s\geq 2\), NEWLINE\[NEWLINEi(F)\leq\begin{cases} 5 ^k\text{ if }S=2k\geq 2\text{ is even}\\ 9.5^{k-1}, \text{ if }s=2k+1\geq 3\text{ is odd}.\end{cases}NEWLINE\]NEWLINE Moreover, for \(F\in\mathcal F_{m,s}\) then \(i(F)\geq f(m,s)\) if and only if \(F=F(m,s)\).NEWLINE When \(s\) is odd and greater than or equal to 3, \(f(m,s)>f(m,s+1)>f^\prime(m,s)>f^\prime(m,s+1)>f(m,s+2)\) and when, \(m\geq s\geq 4\). Suppose \(F\in\mathcal F_{m,s}\) having \(F\neq F(m,s)\) and \(F\neq F^\prime(m,s)\) then \(i(F)<f^\prime(m,s)\). Next, a condition for attaining is given, when \(s\) is odd and greater than 3, \(f(m,s)>f(m,s+1)>f^\prime(m,s)>f^\prime(m,s+1)>f(m,s+2)\) and when \(m\geq s\geq 4\), suppose \(F\in\mathcal F_{m,s}\) having \(F\neq F(m,s)\) and \(F\neq F'(m,s)\) then \(i(F)<f^\prime(m,s)\). This is a sufficient condition for \(F=F^\prime(m,s)\). Another sufficient condition is given for \(s\leq 5\) or \(F=F(m,6)\). The union of \(T^\prime(4)\) and \((m-4)S_1\) is also attained for \(F\neq F^\prime(m,s)\), \(F\neq F^\prime(m,s)\), \(i(F)\geq 40 3^{m-5}\). The only theorem giving the first ten largest numbers of independent sets is stated as follows: NEWLINENEWLINETheorem. Suppose that \(\mathcal F(m)\) is the set of all \(S_0\) free forests of size \(m\geq 6\). Suppose that \(f^{( i )}(m)\) is the \(i\)th largest number of independent sets in \(\mathcal F(m)\) and \(F^{(i)}(m)\in\mathcal F(m)\) with \((F^{(i)}(m)=f^{(i)}(m))\) for \(1\leq i\leq 10\), then we have the following results: NEWLINENEWLINENEWLINE (1) \(f^{(1)}(m)=3 m\), and \(F^{(1)}(m)=mS_1\),NEWLINENEWLINENEWLINE (2) \(f^{(2)}(m)=f (m,2)=5.3^{m- 2}\) and \(F^{( 2 )}(m)=F(m,2)=S_2\cup (m-2)S_1\),NEWLINENEWLINENEWLINE (3) \(f^{(3)}(m)=f(m,3)=9.3^{m-3}\) and \(F^{(3)}(m)=F(m,3)=S\cup (m-3)S_1\),NEWLINENEWLINENEWLINE (4) \(f^{(4)}(m)=f(m,4)=25.3^{m-4}\) and \(F^{(4)}(m)=F(m,4)=2S_2\cup (m-4)S_1\),NEWLINENEWLINENEWLINE (5) \(f^{(5)}(m)=f^\prime(m,3)=8.3^{m-3}\) and \(F^{(5)}(m)=F^\prime(m,3)=P_3\cup (m-3)S_1\),NEWLINE NEWLINENEWLINE(6) \(f^{(6)} (m)=f^\prime(m,4)=17.3^{m-4}\) and \(F^{(6)}(m)=F^\prime(m,4)=S_4\cup (m-4)S_1\),NEWLINENEWLINENEWLINE(7) \(f^{(7)}(m)=f(m,5)=45.3^{m-5}\) and \(F^{(7)}(m)=F(m,5)=S_3\cup S_2\cup (m-5)S_1\),NEWLINENEWLINENEWLINE(8) \(f^{(8)}(m)=14.3^{m-4}\) and \(F^{(8)}(m)=T^\prime(4)\cup (m-4)\),NEWLINENEWLINENEWLINE (9) \(f^{(9)}(m)=f(m,6)=125.3^{m-6}\) and \(F^{(9)}(m)=F(m,6)=3S_2\cup (m-6)S_1\),NEWLINENEWLINENEWLINE(10) \(f^{(10)}(m)=f'(m,5)=40.3^{m-5}\) and \(F^{(10)}(m)=F^\prime(m,6)=P_3\cup S_2\cup (m-5)S_1\).NEWLINENEWLINENEWLINE The references supplied gives information in connection with stochastic models of computer systems, partitions and Fibonacci numbers, topological methods in chemistry extremal problems for topological indices in combinatorial chemistry are noteworthy to mention.