Premium
Continuous k ‐to‐1 functions between complete graphs whose orders are of a different parity
Author(s) -
Gauci John Baptist,
Hilton Anthony J. W.
Publication year - 2010
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20464
Subject(s) - mathematics , combinatorics , integer (computer science) , parity (physics) , order (exchange) , function (biology) , discrete mathematics , physics , finance , particle physics , evolutionary biology , computer science , economics , biology , programming language
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.