- Title
- Small 2-coloured path decompositions
- Creator
- Alspach, Brian; Dyer, Danny; Heinrich, Kathy
- Relation
- ARS Combinatoria Vol. 103, p. 279-288
- Publisher
- Charles Babbage Research Centre
- Resource Type
- journal article
- Date
- 2012
- Description
- Consider a complete graph of multiplicity 2, where between every pair of vertices there is one red and one blue edge. Can the edge set of such a graph be decomposed into isomorphic copies of a 2-coloured path of length 2k that contains k red and k blue edges? A necessary condition for this to be true is n(n -1) ≡ 0 mod 2k. We show that this is sufficient for k≦3.
- Subject
- graph decompositions; mathematical puzzles; graph theory; "Nine Prisoner Problem"
- Identifier
- http://hdl.handle.net/1959.13/1336641
- Identifier
- uon:27669
- Identifier
- ISSN:0381-7032
- Language
- eng
- Reviewed
- Hits: 3472
- Visitors: 2000
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|