Perfect packings with complete graphs minus an edge

Details Perfect packings with complete graphs minus an edge Perfect packings with complete graphs minus an edge

2006-05-08

arxiv.org/abs/math/0605189v1

Mathematics

Combinatorics

Scientific paper

Let K_r^- denote the graph obtained from K_r by deleting one edge. We show that for every integer r\ge 4 there exists an integer n_0=n_0(r) such that every graph G whose order n\ge n_0 is divisible by r and whose minimum degree is at least (1-1/chi_{cr}(K_r^-))n contains a perfect K_r^- packing, i.e. a collection of disjoint copies of K_r^- which covers all vertices of G. Here chi_{cr}(K_r^-)=r(r-2)/(r-1) is the critical chromatic number of K_r^-. The bound on the minimum degree is best possible and confirms a conjecture of Kawarabayashi for large n.

Affiliated with

Also associated with

No associations

Rating

Perfect packings with complete graphs minus an edge does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Perfect packings with complete graphs minus an edge, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Perfect packings with complete graphs minus an edge will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-463517