The dimension of the negative cycle vectors of a signed graph

Alex Schaefer, Thomas Zaslavsky

Abstract


A signed graph is a graph Γ with edges labeled “+” and “−”. The sign of a cycle is the product of its edge signs. Let SpecC(Γ) denote the list of lengths of cycles in Γ. We equip each signed graph with a vector whose entries are the numbers of negative k-cycles for k ∈ SpecC(Γ). These vectors generate a subspace of ℝ|SpecC(Γ)|. 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 ℝ|SpecC(Γ)|.

Keywords


Signed graph, negative cycle vector, permutable matching

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.1605.43f

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications