Generalized One-to-One Mappings between Homomorphism Sets of Digraphs
Author:
Preprint
Abstract
Structural properties of finite digraphs $R$ and $S$ are studied which enforce $\# {\cal H}(G,R) \leq \# {\cal H}(G,S)$ for every finite digraph $G \in \mathfrak{ D }'$, where ${\cal H}(G,H)$ is the set of homomorphisms from $G$ to $H$, and $\mathfrak{ D }'$ is a class of digraphs. In a previous study, we have seen that the key for such a relation between $R$ and $S$ is the existence of a strong S-scheme from $R$ to $S$. Such an S-scheme $\rho$ defines a one-to-one mapping $\rho_G : {\cal S}(G,R) \rightarrow {\cal S}(G,S)$ for every $G \in \mathfrak{ D }'$, where ${\cal S}(G,H)$ is the set of homomorphisms from $G$ to $H$ mapping proper arcs of $G$ to proper arcs of $H$. In the present article, we characterize S-schemes $\rho$ which are induced by strict homomorphisms $\epsilon : {\cal E}(R) \rightarrow {\cal E}(S)$ between auxiliary systems of $R$ and $S$, and we analyze the mutual dependency between the properties of $\rho$ and $\epsilon$. Wide applicability of the theory is ensured by specifying the auxiliary systems ${\cal E}(R)$ and ${\cal E}(S)$ as EV-systems of $R$ and $S$. The results are applied on a rearrangement method for digraphs and on undirected graphs.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Convergent sequences of dense graphs II. Multiway cuts and statistical physicsAnnals of Mathematics, 2012
- On recognizing graphs by numbers of homomorphismsJournal of Graph Theory, 2010
- Graph invariants in the spin modelJournal of Combinatorial Theory, Series B, 2009
- Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testingAdvances in Mathematics, 2008
- Contractors and connectors of graph algebrasJournal of Graph Theory, 2008
- The rank of connection matrices and the dimension of graph algebrasEuropean Journal of Combinatorics, 2006
- Reflection positivity, rank connectivity, and homomorphism of graphsJournal of the American Mathematical Society, 2006
- Distinguishing graphs by the number of homomorphismsDiscussiones Mathematicae Graph Theory, 1995