Article ID Journal Published Year Pages File Type
6872533 Discrete Applied Mathematics 2014 6 Pages PDF
Abstract
Let s and k be two integers with 0≤s≤k and let G be a simple graph of order n. This paper investigates clique partition problems. It is proved that if n≥3s+4(k−s) and d(u)+d(v)≥3(n−s)/2+k−1 for any pair of non-adjacent vertices u,v of G, then G contains s vertex-disjoint K3s and k−s vertex-disjoint K4s such that all of them are vertex-disjoint. Moreover, the degree condition is sharp.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,