Abstract | ||
---|---|---|
In this paper we use independent generalized degree conditions imposed on K (1, m )-free graphs (for an integer m ⩾3) to obtain results involving β( G ), the vertex independence number of G . We determine that in a K (1, m )-free graph G of order n if the cardinality of the neighborhood union of pairs of non-adjacent vertices is a positive fraction of n , then β( G ) is bpunded and independent of n . In particular, we show that if G is a K (1, m )-free graph of order n such that the cardinality of the neighborhood union of pairs of non-adjacent vertices is at least r , then β( G )⩽ s , where s is the larger solution to rs ( s −1)=( n − s )( m −1)(2 s − m ). We also explore the relationship between β( G ) and δ( G ) (the minimum degree) in K (1, m )-free graphs and provide a generalization for degree sums of sets of more than one vertex. |
Year | DOI | Venue |
---|---|---|
1992 | 10.1016/0012-365X(92)90035-E | Discrete Mathematics |
Keywords | Field | DocType |
m-free graph,independence number,independent generalized degree | Integer,Discrete mathematics,Graph,Combinatorics,Independence number,Vertex (geometry),Generalization,Cardinality,Degree (graph theory),Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
103 | 1 | Discrete Mathematics |
Citations | PageRank | References |
8 | 1.04 | 5 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
R. J. Faudree | 1 | 174 | 38.15 |
R. J. Gould | 2 | 23 | 4.92 |
M. S. Jacobson | 3 | 198 | 40.79 |
L. M. Lesniak | 4 | 44 | 8.23 |
T. E. Lindquester | 5 | 8 | 1.04 |