On a neighborhood condition implying the existence of disjoint complete graphs (Q911615): Difference between revisions

The neighbourhood \(N_ G(x)\) of a vertex x in a graph G is the set of all vertices which are adjacent to x in G. The p-neighbourhood condition \(NC_ p(G)\) is the minimum of cardinalities of the sets \(\cup^{p}_{i=1}N_ G(x_ i)\) taken over all independent subsets \(\{x_ 1,x_ 2,...,x_ p\}\) of the vertex set of G. The main theorem states a sufficient condition for the existence of t pairwise vertex- disjoint complete subgraphs with m vertices in a graph with n vertices; this condition is formulated by means of \(NC_ p(G)\).