The Dimension of the Negative Cycle Vectors of Signed Graphs

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 $\mathrm{SpecC}(\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 $k\in \mathrm{SpecC}(\Gamma )$. These vectors generate a subspace of ${\mathbb{R}}^{\mathrm{SpecC}(\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}}^{\mathrm{SpecC}(\Gamma )}$.

15 pp., 3 figures