Switching classes of directed graphs

alternating function cyclic triple covers of the complete digraph enumeration Mallows-Sloane Theorem switching classes of digraphs switching equivalent digraphs two-digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Review text

A simple digraph on a finite set X may be defined as an alternating function \(\tau\) :X\(\times X\to GF(3)\), i.e., \(\tau (x,y)=-\tau (y,x)\) for all x,y\(\in X\). Two digraphs \(\tau\),\(\mu\) are said to be switching equivalent if there is a function f of X into GF(3) such that \(\tau (x,y)=\mu (x,y)+f(x)-f(y)\) for all x,y\(\in X\). Equivalence classes are called two-digraphs. An automorphism of a two-digraph \(\Gamma\) is a permutation of X mapping any (or equivalently, some) digraph in \(\Gamma\) to another digraph in \(\Gamma\). In particular, an automorphism of a digraph is an automorphism of its switching class. In the present paper we discuss switching classes of digraphs on X and their equivalent formulations, two-digraphs and cyclic triple covers of the complete digraph. We show that an appropriate analogue of the Mallows-Sloane Theorem holds. We find a necessary and sufficient condition that a cyclic group of automorphisms of a switching class of digraphs be representable as an automorphism group of the triple cover. We present an enumeration of the isomorphism types of switching classes of digraphs. Finally we show how to characterize the permutations which fix digraphs in all switching classes they fix.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Switching classes of directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1058524)