Digraphs having the same canonical double covering (Q1367047)

The paper studies directed graphs having the same canonical double cover. If \(\Gamma\) is a digraph, then the canonical double cover \(B(\Gamma)\) of \(\Gamma\) is the digraph whose vertex set is \(V(\Gamma)\times\{1,2\}\) and in which edges go from \((u,0)\) to \((v,1)\) and from \((u,1)\) to \((v,0)\) whenever an edge goes from \(u\) to \(v\) in \(\Gamma\). An involutory automorphism \(a\) of a bipartite digraph \(\Gamma\) is called switching, if it interchanges the bipartition classes of \(\Gamma\). If moreover no edge joins \(u\) with \(a(u)\) for any vertex \(u\) of \(\Gamma\), then \(a\) is strongly switching. The main theorem asserts that for a given bipartite digraph \(\widetilde\Gamma\) the number of non-isomorphic graphs \(\Gamma\) such that \(\widetilde\Gamma\cong B(\Gamma)\) is equal to the number of conjugacy classes of switching involutory automorphisms in the automorphism group \(\Aut(\widetilde\Gamma)\), and the number of non-isomorphic loopless graphs \(\Gamma\) such that \(\widetilde\Gamma\cong B(\Gamma)\) is equal to the number of conjugacy classes of strongly switching involutory automorphisms of \(\widetilde\Gamma\) in \(\Aut(\widetilde\Gamma)\).