Continuous k-to-1 functions between complete graphs whose orders are of a different parity
✍ Scribed by John Baptist Gauci; Anthony J. W. Hilton
- Publisher
- John Wiley and Sons
- Year
- 2009
- Tongue
- English
- Weight
- 216 KB
- Volume
- 65
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
A function between graphs is k-to-1 if each point in the codomain has precisely k pre-images in the domain. Given two graphs, G and H, and an integer k ≥ 1, and considering G and H as subsets of R 3 , there may or may not be a k-to-1 continuous function (i.e. a k-to-1 map in the usual topological sense) from G onto H. In this paper we consider graphs G and H whose order is of a different parity and determine the even and odd values of k for which there exists a k-to-1 map from G onto H. We first consider k-to-1 maps from K 2r onto K 2s+1 and prove that for 1 ≤ r ≤ s, (r, s) = (1, 1), there is a continuous k-to-1 map for k even if and only if k ≥ 2s and for k odd if and only if k ≥ s o (where s o indicates the next odd integer greater than or equal to s). We then consider k-to-1 maps from K 2s+1 onto K 2s . We show that for 1 ≤ r < s, such a map exists for even Journal of Graph Theory ᭧ 2009 Wiley Periodicals, Inc.
values of k if and only if k ≥ 2s. We also prove that whatever the values of r and s are, no such k-to-1 map exists for odd values of k. To conclude, we give all triples (n, k, m) for which there is a k-to-1 map from K n onto K m in the case when n ≤ m.