Quasi-isomorphisms and quasi-cyclic graphs

Abstract

We consider (directed) graphs. A graph morphism f : G -> H is called a quasi-isomorphism if each morphism from a cyclic graph C_n to H can be lifted uniquely along f, i.e. if (C_n,f) : (C_n,G)_Gph -> (C_n,H)_Gph is bijective for each n > 0. A subgraph is called quasi-cyclic if it is the image of a cyclic graph under a graph morphism. Several lifting results for a quasi-isomorphism f: G -> H are shown:

A cyclic subgraph of H can be lifted uniquely along f to a cyclic subgraph of G, and the pertaining restriction of f is an isomorphism. If G is finite, then lifting two cyclic subgraphs of H with at least one vertex in common, we obtain two cyclic subgraphs of G contained in a common quasi-cyclic subgraph of G. Each quasi-cyclic subgraph of H can be lifted to a quasi-cyclic subgraph of G having the same circonferential length. If G and H are finite, then each maximal quasi-cyclic subgraph of H can be lifted uniquely to a maximal quasi-cyclic subgraph of G. Moreover, a necessary and sufficient criterion for a graph morphism between finite graphs to be a quasi-isomorphism is given, involving pullbacks and adjacency matrices; this criterion can be verified using a finite algorithm and is implemented in Magma.