Abstract
For a positive integer r ≥ 2, a Kr -factor of a graph is a collection vertex-disjoint copies of Kr 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 Kr -factor. In this note, we propose investigating the relation between minimum degree and existence of perfect Kr -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(r2)? 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