Independence number and \(k\)-trees of graphs
Let \(G=(V,E)\) be a simple graph and let \(\alpha(G)\) and \(\kappa(G)\) denote the independence number and the connectivity of \(G\). For two vertices \(x\) and \(y\) of \(G\), the local connectivity \(\kappa_G(x,y)\) is defined to be the maximum number of internally disjoint paths connecting \(x\) and \(y\) and define \(\kappa_G(S):= \min\{\kappa_G(x,y): x,y\in S, x\neq y\}\), where \(S\) is a subset of \(V(G)\). The author in this paper has shown that if \(\alpha(G)\leq (k-1)\kappa_G(S)+1\), then \(G\) has a tree which contain \(S\) and its maximum degree is at most \(k\). Moreover this condition is sharp.
scientific article; zbMATH DE number 6817801