2020/04/24 by Frank a Campo, Campo, Frank a
Mathematics · #06A07 (Primary) 06A06 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:06A06 #msc:06A07
paper · pdf · doi:10.48550/arxiv.2004.11653
27 pages, 3 figures
arxiv created 2021/03/10 · arxiv updated 2021/03/11
For digraphs G and H, let \cal H(G,H) be the set of all homomorphisms from G to H, and let \cal S(G,H) be the subset of those homomorphisms mapping all proper arcs in G to proper arcs in H. From an earlier investigation we know that for certain digraphs R and S, the relation "# \cal S(G,R) ≤ # \cal S(G,S) for all G ∈ \mathfrak D '" implies "# \cal H(G,R) ≤ # \cal H(G,S) for all G ∈ \mathfrak D '", where \mathfrak D ' is a subclass of digraphs. Now we ask for the inverse: For which digraphs R, S and which subclasses \mathfrak D ' of digraphs does "# \cal H(G,R) ≤ # \cal H(G,S) for all G ∈ \mathfrak D '" imply "# \cal S(G,R) ≤ # \cal S(G,S) for all G ∈ \mathfrak D '"? We prove this implication for three combinations of digraph classes. In particular, the relations are equivalent for all flat posets R, S with respect to all flat posets G.