On independent generalized degrees and independence numbers in \(K(1,m)\)- free graphs
A graph is \(K(1,m)\)-free if it contains no induced subgraph isomorphic to \(K(1,m)\). It is shown that if \(G\) is a \(K(1,m)\)-free graph on \(n\) vertices such that the cardinality of the neighbourhood union of pairs of nonadjacent vertices is at least \(r\), then the independence number \(\beta(G)\leq s\), where \(s\) is the largest solution to \(rs(s-1)=(n-s)(m- 1)(2s-m)\). It is then shown that if \(G\) is a \(K(1,m)\)-free graph on \(n\) vertices with minimum degree \(\delta(G)\), then \(\beta(G)\leq(m- 1)n/(\delta(G)+m-1)\). Suppose \(p\) is an integer such that \(1\leq p\leq\beta(G)\). Then \(\sigma_ p=\min\{\sum_{v\in P}\deg v\}\) where the minimum is taken over all independent sets \(P\subset V(G)\) such that \(| P|=p\). It is shown that if \(G\) is a \(K(1,m)\)-free graph of order \(n\) such that \(\sigma_ p=px\) for some \(p\) with \(1\leq p\leq\beta(G)\), then \(\beta(G)\leq(m-1)n/(x+m-1)\).
scientific article; zbMATH DE number 89514
scientific article