pith. sign in

arxiv: 1412.2947 · v1 · pith:3YXJOOOEnew · submitted 2014-12-09 · 🧮 math.CO

On a test on switching separability of graphs modulo q

classification 🧮 math.CO
keywords graphswitchingseparabilityseparabletestverticesadditivecalled
0
0 comments X
read the original abstract

We consider the graphs whose edges are marked by the integers (weights) from $0$ to $q-1$ (zero corresponds to no-edge). Such graph is called additive if its vertices can be marked in such a way that the weight of every edge is equal to the modulo-$q$ sum of weights of the two incident vertices. By a switching of a graph we mean the modulo-$q$ sum of the graph with some additive graph on the same vertex set. A graph with $n$ vertices is called switching separable if some of its switchings does not have a connected component of order $n$ or $n-1$. We consider the following test for the switching separability: if removing any vertex of a graph $G$ results in a switching separable graph, then $G$ is switching separable itself. We prove this test for odd $q$ and characterize the exceptions when $q$ is even. We establish a connection between the switching separability of a graph and the reducibility of $(n-1)$-ary quasigroups constructed from this graph.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.