Pairwise Compatible Hamilton Decompositions ofKn
✍ Scribed by H Verrall
- Book ID
- 102583096
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 363 KB
- Volume
- 79
- Category
- Article
- ISSN
- 0097-3165
No coin nor oath required. For personal study only.
✦ Synopsis
In this paper we prove that there are either 2k&2 or 2k&1 pairwise compatible Hamilton path decompositions of K 2k . In the case of K 4 , there exactly 2 compatible Hamilton path decompositions. We also find (different) lower bounds on the number of pairwise compatible Hamilton decompositions of K 4m+1 and K 4m+3 .
1997 Academic Press
1. INTRODUCTION AND NOTATION
Definitions not included here are as in [3,8]. Let G be a finite graph. A 2-path is a sequence v 0 , v 1 , v 2 , where v 0 , v 1 , v 2 # V(G), and v 0 {v 1 { v 2 {v 0 . We write it as v 0 v 1 v 2 and say it is centred at v 1 with end vertices v 0 and v 2 . The proofs in this paper rely on the fact that a trail or a tour can be described uniquely by the set of 2-paths it contains. We call two trails (or tours) t 1 and t 2 in G similar if there exists an automorphism \ of
We call two Hamilton decompositions of K 2k+1 compatible if they have no 2-path in common. Similarly, we call two Hamilton path decompositions of K 2k compatible if they have no 2-path in common. We call a set of 2k&1 pairwise compatible Hamilton (path) decompositions of K 2k+1 (K 2k ), a perfect set of Hamilton ( path) decompositions of K 2k+1 (K 2k ).
The results in this paper were motivated by a question of Kotzig's [6]:
). What is the smallest k>1 for which there is a perfect set of Hamilton decompositions of K 2k+1 ? It is possible that no such k exists. It is not hard to show that there cannot be two compatible Hamilton decompositions of K 5 , let alone three article no. TA972777 209 0097-3165Â97 25.00