“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 2347  


Abstract:  
Let F be a graph of order at most k. We prove that for any
integer g there is a graph G of girth at least g and of
maximum degree at most 5k^{13} such that G admits a surjective
homomorphism c to F, and moreover, for any Fpointed graph
H (see definition below) with at most k vertices, and for any
homomorphism h from G to H there is a unique homomorphism
f from F to H such that h=f °c. As a consequence, we
prove that if H is a projective graph of order k, then for any
finite family F of prescribed mappings from a set X to
V(H) (with F = t), there is a graph G of arbitrary
large girth and of maximum degree at most 5k^{26mt} (where m = X) such that X ⊆ V(G) and up to an automorphism of
H, there are exactly t homomorphisms from G to H, each of
which is an extension of an f ∈ F.
Download TeX format 

back to top 