The dimension of the negative cycle vectors of a signed graph - Schaefer, Alex (Ars mathematica contemporanea, 2019)
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 \in SpecC(Γ)$?. These vectors generate a subspace of ?$\mathbb{R}^{|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 ?$\mathbb{R}^{|SpecC(Γ)|}$?.
Keywords: negative cycle vector; permutabilno prirejanje; permutable matching; predznačeni graf; signed graph; vektor negativnih ciklov