Continuous k ‐to‐1 functions between complete graphs whose orders are of a different parity

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 ℝ 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 2 r onto K 2 s +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 ≥2 s 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 2 s +1 onto K 2 s . We show that for 1≤ r < s , such a map exists for even values of k if and only if k ≥2 s . 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 . © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 35–60, 2010.