The Negative Cycle Vectors of Signed Complete Graphs

Abstract

A signed graph is a graph where the edges are assigned labels of either "$+$" or "$-$". The sign of a cycle in the graph is the product of the signs of its edges. We equip each signed complete graph with a vector whose entries are the number of negative $k$-cycles for $k\in \{3,\dots ,n\}$. These vectors generate an affine subspace of ${\mathbb{R}}^{n-2}$. We prove that this subspace is all of ${\mathbb{R}}^{n-2}$.

Superseded by arxiv:1706.09041, a more general, multi-author version

Cited by in corpus (1)

• Negative Circles in Signed Graphs: A Problem Collection