IPM

“ Schools ”

“ Centers and Units ”

“ Research Groups ”

“ Useful Links ”

“ E-Services ”

“School of Mathematics”

Paper IPM / M / 2340

School of Mathematics

Title:

Graph homomorphisms through random walks

Author(s):

1 .	A. Daneshgar
2 .	H. Hajiabolhassan

Status:

Published

Journal:

J. Graph Theory

No.:

Vol.:

Year:

2003

Pages:

15-38

Supported by:

IPM

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