Fractional multiples of graphs and the density of vertex-transitive graphs

摘要

We introduce a construction called the fractional multiple of a graph. This construction is used to settle a question raised by E. Welzl: We show that if G and H are vertex-transitive graphs such that there exists a homomorphism from G to H but no homomorphism from H to G, then there exists a vertex-transitive graph that is homomorphically 'in between' G and H.