Homomorphisms of Cayley graphs and Cycle Double Covers

2019/01/10 by Radek Hušek, Robert Šámal, Hušek, Radek +1
Computer Science · Mathematics · #05C21 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #msc:05C21

paper · pdf · doi:10.48550/arxiv.1901.03112

arxiv created 2019/01/10 · arxiv updated 2019/01/11

Abstract

We study the following conjecture of Matt DeVos: If there is a graph homomorphism from Cayley graph Cay(M, B) to another Cayley graph Cay(M', B') then every graph with an (M, B)-flow has an (M', B')-flow. This conjecture was originally motivated by the flow-tension duality. We show that a natural strengthening of this conjecture does not hold in all cases but we conjecture that it still holds for an interesting subclass of them and we prove a partial result in this direction. We also show that the original conjecture implies the existence of an oriented cycle double cover with a small number of cycles.

Related

• Flows that are sums of hamiltonian cycles in Cayley graphs on abelian groups
• Directed cycle double covers and cut-obstacles
• Flow-continuous mappings -- influence of the group
• A Simple Proof for the Cycle Double Cover Conjecture
• Weak embedding theorem and a proof of cycle double cover of bridgeless graphs