# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Graph homomorphisms and nodal domains. (English) Zbl 1104.05044
Summary: 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.

##### MSC:
 05C50 Graphs and linear algebra
##### Keywords:
graph spectra; $G$-design
Full Text:
##### References:
 [1] De Verdiére, Y. Colin: Spectres de graphes. Cours spécialisés 4 (1998) [2] Colbourn, C. J.; Dinitz, J. H.: CRC handbook of design theory. (1996) · Zbl 0836.00010 [3] Cvetković, D. M.; Doob, M.; Sachs, H.: Spectra of graphs. (1980) · Zbl 0458.05042 [4] Cvetković, D. M.; Rowlinson, P.; Simić, S.: Eigenspaces of graphs. (1997) · Zbl 0878.05057 [5] Daneshgar, A.; Hajiabolhassan, H.: Random walks and graph homomorphisms. AMS Proceedings DIMACS series 63, 49-63 (2004) · Zbl 1064.05098 [6] Daneshgar, A.; Hajiabolhassan, H.: Graph homomorphims through random walks. J. graph theory 44, 15-38 (2003) · Zbl 1030.60061 [7] A. Daneshgar, H. Hajiabolhassan, Circular chromatic number through algebraic no-homomorphism theorems, Manuscript, 2003. · Zbl 1030.60061 [8] Davies, E. B.; Gladwell, G. M. L.; Leydold, J.; Stadler, P. F.: Discrete nodal domain theorems. Linear algebra appl. 336, 51-60 (2001) · Zbl 0990.05093 [9] Duval, A. M.; Reiner, V.: Perron-Frobenius type results and discrete versions of nodal domain theorems. Linear algebra appl. 294, 259-268 (1999) · Zbl 0938.15002 [10] Godsil, C. D.; Royle, G.: Algebraic graph theory. Grad texts in math. 207 (2001) · Zbl 0968.05002 [11] Hahn, G.; Tardif, C.: G.hahng.sabidussigraph homomorphisms: structure and symmetry. NATO adv. Sci. inst. Ser. C math. Phys. sci. 497, 107-167 (1997) · Zbl 0880.05079 [12] Hell, P.: Algorithmic aspects of graph homomorphisms. London math. Soc. lecture note ser. 307, 239-276 (2003) · Zbl 1035.05089 [13] Den Heuvel, J. Van: Hamilton cycles and eigenvalues of graphs. Linear algebra appl. 226-228, 723-730 (1995) [14] Horn, R.; Johnson, C.: Matrix analysis. (1985) · Zbl 0576.15001 [15] Lamken, E. R.; Wilson, R. M.: Decomposition of edge-colored complete graphs. J. combin. Theory ser. A 89, 149-200 (2000) · Zbl 0937.05064 [16] Mohar, B.: A domain monotonicity theorem for graphs and hamiltonicity. Disc. appl. Math. 36, 169-177 (1992) · Zbl 0765.05071 [17] Quattrocchi, G.: Embedding G1-designs into G2-designs, a short survey. Rend. sem. Mat. messina ser. II 8, No. Suppl. 24, 129-143 (2002) · Zbl 1042.05016 [18] Saloff-Coste, L.: Lectures on finite Markov chains. Lecture notes in math. 1665, 304-413 (1997) · Zbl 0885.60061