## Abstract

For a positive integer r ≥ 2, a K_{r} -factor of a graph is a collection vertex-disjoint copies of K_{r} which covers all the vertices of the given graph. The celebrated theorem of Hajnal and Szemerédi asserts that every graph on n vertices with minimum degree at least (1-1/r)n contains a K_{r} -factor. In this note, we propose investigating the relation between minimum degree and existence of perfect K_{r} -packing for edge-weighted graphs. The main question we study is the following. Suppose that a positive integer r ≥ 2 and a real t ε [0, 1] is given. What is the minimum weighted degree of Kn that guarantees the existence of a K _{r} -factor such that every factor has total edge weight at least t(^{r}_{2})? We provide some lower and upper bounds and make a conjecture on the asymptotics of the threshold as n goes to infinity.

Original language | English (US) |
---|---|

Pages (from-to) | 346-350 |

Number of pages | 5 |

Journal | Combinatorics Probability and Computing |

Volume | 22 |

Issue number | 3 |

DOIs | |

State | Published - May 2013 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics