On one test for the switching separability of graphs modulo q

DOI10.1134/S003744661601002XzbMATH Open1338.05211arXiv1412.2947OpenAlexW3100811678MaRDI QIDQ299150FDOQ299150

Authors: Evgeniĭ Andreevich Bespalov, Denis S. Krotov 

Publication date: 22 June 2016

Published in: Siberian Mathematical Journal (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1412.2947

Recommendations

• On a connection between the switching separability of a graph and that of its subgraphs
• On switching nonseparable graphs with switching separable subgraphs
• Switching in one-factorisations of complete graphs
• On the separability of graphs
• scientific article; zbMATH DE number 3912422
• Complete multipartite graphs that are determined, up to switching, by their Seidel spectrum
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• Testing the \((s,t)\) connectivity of graphs and digraphs
• On the power of a perturbation for testing non-isomorphism of graphs
• A combinatorial characterization of the testable graph properties, it's all about regularity

zbMATH Keywords

separability\(n\)-ary quasigroupSeidel switching

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• On irreducible \(n\)-ary quasigroups with reducible retracts.
• On reducibility of \(n\)-ary quasigroups
• \(n\)-ary quasigroups of order 4.
• Title not available (Why is that?)
• On connection between reducibility of an \(n\)-ary quasigroup and that of its retracts.
• Associativity in multiary quasigroups: The way of biased expansions
• Positivity for explicit two-step methods in linear multistep and one-leg form
• On switching nonseparable graphs with switching separable subgraphs

Cited In (1)

• On a connection between the switching separability of a graph and that of its subgraphs

This page was built for publication: On one test for the switching separability of graphs modulo \(q\)

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