✦ LIBER ✦

Graph homomorphisms and nodal domains

✍ Scribed by Amir Daneshgar; Hossein Hajiabolhassan

Publisher: Elsevier Science
Year: 2006
Tongue: English
Weight: 137 KB
Volume: 418
Category: Article
ISSN: 0024-3795
DOI: 10.1016/j.laa.2006.01.023

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we derive some necessary spectral conditions for the existence of graph homomorphisms in which we also consider some parameters related to the corresponding eigenspaces such as nodal domains. In this approach, we consider the combinatorial Laplacian and co-Laplacian as well as the adjacency matrix. Also, we present some applications in graph decompositions where we prove a general version of Fisher's inequality for G-designs.

📜 SIMILAR VOLUMES

Independence and graph homomorphisms gra

Independence and graph homomorphisms graph homomorphisms

✍ Michael O. Albertson; Lily Chan; Ruth Haas 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 305 KB

## Abstract A graph with __n__ vertices that contains no triangle and no 5‐cycle and minimum degree exceeding __n__/4 contains an independent set with at least (3__n__)/7 vertices. This is best possible. The proof proceeds by producing a homomorphism to the 7‐cycle and invoking the No Homomorphism

Geometric graph homomorphisms

✍ Debra L. Boutin; Sally Cockburn 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB

## Abstract A __geometric graph__ is a simple graph drawn on points in the plane, in general position, with straightline edges. A __geometric__ __homomorphism__ from to is a vertex map that preserves adjacencies and crossings. This work proves some basic properties of geometric homomorphisms and

Graph Homomorphisms and Phase Transition

Graph Homomorphisms and Phase Transitions

✍ Graham R. Brightwell; Peter Winkler 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 627 KB

We model physical systems with ``hard constraints'' by the space Hom(G, H) of homomorphisms from a locally finite graph G to a fixed finite constraint graph H. For any assignment \* of positive real activities to the nodes of H, there is at least one Gibbs measure on Hom(G, H); when G is infinite, t

Graph homomorphisms through random walks

✍ Amir Daneshgar; Hossein Hajiabolhassan 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB

## 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 interl

Path homomorphisms, graph colorings, and

Path homomorphisms, graph colorings, and boolean matrices

✍ Jaroslav Nešetřil; Claude Tardif 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 124 KB

## Abstract We investigate bounds on the chromatic number of a graph __G__ derived from the nonexistence of homomorphisms from some path \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray\*}\vec{P}\end{eqnarray\*}\end{document} into some orientation \documentclass{

The complexity of counting graph homomor

The complexity of counting graph homomorphisms

✍ Martin Dyer; Catherine Greenhill 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 229 KB