On independent generalized degrees and independence numbers in \(K(1,m)\)- free graphs
type: Item
instance of: scholarly article
title: On independent generalized degrees and independence numbers in \(K(1,m)\)- free graphs
zbMATH Open document ID: 0755.05035
DOI: 10.1016/0012-365X(92)90035-E
author: Ralph Faudree
author: Ronald Gould
author: Michael Jacobson
author: T. E. Lindquester
author: Linda Lesniak
published in: Discrete Mathematics
publication date: 1993-01-16T00:00:00Z
review text: 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)\).
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 89514
zbMATH Keywords: independent generalized degrees
zbMATH Keywords: \(K(1,m)\)-free graphs
zbMATH Keywords: neighbourhood union
zbMATH Keywords: independence number
reviewed by: Ortrud R. Oellermann
MaRDI profile type: Publication
cites work: Hamiltonian properties of graphs with large neighborhood unions
cites work: Q4029984
cites work: Neighborhood unions and a generalization of Dirac's theorem
cites work: Q3363384
cites work: Neighbourhood unions and Hamiltonian properties in graphs
cites work: Q4873826
cites work: Q3992558
cites work: Q3491603
cites work: Longest paths and cycles in K1,3-free graphs
Recommended article: Minimum independent generalized \(t\)-degree and independence number in \(K_{1,r+1}\)-free graphs
Recommended article: On the independence number in \(K_{1,r+1}\)-free graphs
Recommended article: On the \(k\)-independence number in graphs
Recommended article: On the \(k\)-independence number of graphs
Recommended article: Some relations between the independence number and other parameters in \(K_{1,r}\)-free graphs
Recommended article: Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees
Recommended article: The independence number of graphs in terms of degrees
Recommended article: Generalized degree conditions for graphs with bounded independence number
Recommended article: Degree multiplicities and independent sets in \(K_ 4\)-free graphs
Recommended article: Q4735212
description: scientific article; zbMATH DE number 89514