A Neighborhood Condition Which Implies the Existence of a Complete Multipartite Subgraph
Document Type
Article
Publication Date
8-1-1993
Description
Given a graph G and uε{lunate}V(G), the neighborhood N(u)={uε{lunate}V(G)|uvε{lunate}E(G)}. We define NCk(G)=min|∪N(ui)| where the minimum is taken over all k independent sets {u1...uk} of vertices in V(G). We shall show that if G is a graph of order n that satisfies the neighborhood condition NCk(G) > d-2 d-1n+cn1- 1 rfor some real number c=c(m, d, k, r) then for sufficiently large n, G contains at least one copy of a K(r,m...md-1) where mi=m for each i and r≥m. When r=1, 2 or 3, this result is best possible.
Citation Information
Faudree, Ralph J.; and Knisley, Debra J.. 1993. A Neighborhood Condition Which Implies the Existence of a Complete Multipartite Subgraph. Discrete Mathematics. Vol.118(1-3). 57-68. https://doi.org/10.1016/0012-365X(93)90053-V ISSN: 0012-365X