Switching classes of directed graphs
type: Item
instance of: scholarly article
title: Switching classes of directed graphs
zbMATH Open document ID: 0565.05034
DOI: 10.1016/0095-8956(86)90075-4
author: Ying Cheng
author: Albert L. jun. Wells
published in: Journal of Combinatorial Theory. Series B
publication date: 1986-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 3900791
zbMATH Keywords: switching equivalent digraphs
zbMATH Keywords: alternating function
zbMATH Keywords: two-digraphs
zbMATH Keywords: switching classes of digraphs
zbMATH Keywords: cyclic triple covers of the complete digraph
zbMATH Keywords: Mallows-Sloane Theorem
zbMATH Keywords: enumeration
MaRDI profile type: Publication
full work available at URL: 0095-8956(86)90075-4
OpenAlex ID: W2083490505
cites work: Cohomological aspects of two-graphs
cites work: Signatures and signed switching classes
cites work: Two-Graphs, Switching Classes and Euler Graphs are Equal in Number
cites work: Q5343374
cites work: Q4121914
cites work: Q3931443
cites work: Q5522742
cites work: Regular 2-Graphs
cites work: Even signings, signed switching classes, and (-1,1)-matrices
cites work: Q4207929
cites work: Q3027057
description: scientific article; zbMATH DE number 3900791