Generating Cwatsets from Multiple Graphs

Abstract

A cwatset is a set of binary row vectors with the property that adding one of the vectors to each vector in the set yields the same result as applying a permutation of the components to each vector in the set. Cwatsets were introduced in the 1990s for statistical purposes but have since gained more importance as an algebraic structure that encompasses the property of “closure with a twist.” As such, their development has shown many parallels to group theory. Bush and Isihara2 described a procedure for representing isomorphs of a simple graph by binary vectors and showed that under this construction any isomorphism class of simple graphs always results in a cwatset. However, not every cwatset can be represented by a graph using the Bush-Isihara construction; in fact, the construction only generates cwatsets with vector lengths that are triangular numbers, row sums that are even, and column sums that take on at most two values. With the objective of representing all cwatsets by graphs, modifications of the Bush- Isihara construction are described by (1) placing restrictions on the isomorphs used, and/or (2) using isomorphs from each graph in a collection of non-isomorphic graphs. In certain cases these modifications both result in cwatsets, and some necessary conditions and sufficient conditions for this to happen are given. The modifications allow the generating of cwatsets with arbitrary vector lengths and row and column sums with several different values.