home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / theory / 1790 < prev    next >
Encoding:
Internet Message Format  |  1992-08-20  |  1.1 KB
  1. Path: sparky!uunet!ogicse!uwm.edu!ux1.cso.uiuc.edu!news.cso.uiuc.edu!west
  2. From: west@symcom.math.uiuc.edu (Douglas West)
  3. Newsgroups: comp.theory
  4. Subject: Re: Round robin problem
  5. Message-ID: <BtB35o.J5@news.cso.uiuc.edu>
  6. Date: 20 Aug 92 23:41:47 GMT
  7. Article-I.D.: news.BtB35o.J5
  8. References: <1992Aug20.170241.22798@src.umd.edu>
  9. Sender: usenet@news.cso.uiuc.edu (Net Noise owner)
  10. Organization: University of Illinois at Urbana
  11. Lines: 13
  12.  
  13. clin@eng.umd.edu (Charles Lin) writes:
  14. >   Sorry, if this is the wrong place to post.
  15. >   Anyone know of a solution to the following problem:
  16. >   Given a complete graph of n nodes (vertices) where n is even, 
  17. >and given n - 1 colors, color the edges so that:
  18. >   each vertex has at least one edge with each of the n - 1 colors
  19.  
  20. This is the problem of showing that K_{2n} is 1-factorable.
  21. It is exercise 5.1.5a and exercise 6.2.1 in the graph theory book of
  22. Bondy and Murty.  The standard construction is in the back of the book.
  23. Put one vertex at the center of a ring of 2n-1 others.  Each matching
  24. consists of one radius and the pairs inducing chords perpendicular to it.
  25. -Doug West
  26.