2019/06/27 by Frank a Campo, Campo, Frank a · 2 citations
Engineering · Mathematics · #06A06 #06A07 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO #msc:06A06 #msc:06A07
paper · pdf · doi:10.48550/arxiv.1906.11758
33 pages, 10 figures
openalex publication_date 2019/06/27 · arxiv created 2020/11/02 · arxiv updated 2020/11/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Structural properties of finite digraphs R and S are studied which enforce # \cal H(G,R) ≤ # \cal H(G,S) for every finite digraph G ∈ \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 ρ defines a one-to-one mapping ρG : \cal S(G,R) → \cal S(G,S) for every G ∈ \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 ρ which are induced by strict homomorphisms ε: \cal E(R) → \cal E(S) between auxiliary systems of R and S, and we analyze the mutual dependency between the properties of ρ and ε. 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.