“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 2340 |
|
||||
| Abstract: | |||||
|
In this paper we introduce some general necessary conditions for
the existence of graph homomorphisms, which hold in both directed
and undirected cases. Our method is a combination of Diaconis and
Saloff-Coste comparison technique for Markov chains and a
generalization of Haemers interlacing theorem. As some
applications, we obtain a necessary condition for the spanning
subgraph problem, which also provides a generalization of a
theorem of Mohar (1992) as a necessary condition for
Hamiltonicity. In particular, in the case that the range is a
Cayley graph or an edge-transitive graph, we obtain theorems with
a corollary about the existence of homomorphisms to cycles. This
specially, provides a proof of the fact that the Coxeter graph is
a core. Also, we obtain some information about the cores of
vertex-transitive graphs.
Download TeX format |
|||||
| back to top | |||||
