“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 2340
School of Mathematics
  Title:   Graph homomorphisms through random walks
1.  A. Daneshgar
2.  H. Hajiabolhassan
  Status:   Published
  Journal: J. Graph Theory
  No.:  1
  Vol.:  44
  Year:  2003
  Pages:   15-38
  Supported by:  IPM
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
scroll left or right