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.

Share

COinS