The dimension of the negative cycle vectors of a signed graph

DOI10.26493/1855-3974.1605.43FMaRDI QIDQ5225061zbMATH OpenOpenAlexWikidataFDO

Authors Alex Schaefer, Thomas Zaslavsky

Publication date 25 July 2019

Published in Ars Mathematica Contemporanea (Search for Journal in Brave)

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

zbMATH Keywords

negative cycle vectorpermutable matchingsigned graph

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A "signed graph" is a graph $Gamma$ where the edges are assigned sign labels, either "$+$" or "$-$". The sign of a cycle is the product of the signs of its edges. Let $mathrmSpecC(Gamma)$ denote the list of lengths of cycles in $Gamma$. We equip each signed graph with a vector whose entries are the numbers of negative $k$-cycles for $kinmathrmSpecC(Gamma)$. These vectors generate a subspace of $mathbb{R}^{mathrmSpecC(Gamma)}$. Using matchings with a strong permutability property, we provide lower bounds on the dimension of this space; in particular, we show for complete graphs, complete bipartite graphs, and a few other graphs that this space is all of $mathbb{R}^{mathrmSpecC(Gamma)}$.

Recommendations

• Negative cycles in complete signed graphs
• scientific article; zbMATH DE number 1958615
• Signed cycle domination numbers of graphs
• The signed cycle domination numbers of a graph and its complement
• On adjacency matrices and descriptors of signed cycle graphs
• The nullity of bicyclic signed graphs
• A method of enumeration of negative cycles of a signed graph
• scientific article; zbMATH DE number 32031
• On signed cycle (vertex) domination in graphs

Cites work

• Frustrated triangles
• Graphs that contain multiply transitive matchings
• scientific article; zbMATH DE number 3512159 (Why is no real title available?)
• scientific article; zbMATH DE number 3547309 (Why is no real title available?)
• Negative cycles in complete signed graphs
• On the notion of balance of a signed graph
• Two-Graphs, Switching Classes and Euler Graphs are Equal in Number

Cited in

(4)

• Addendum to: ``Spectral characterizations of signed cycles
• Graphs that contain multiply transitive matchings
• The dimension of valid distance drawings of signed graphs
• Negative circles in signed graphs: a problem collection

This page was built for publication: The dimension of the negative cycle vectors of a signed graph

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