A signed graph is a graph ?$\Gamma$? with edges labeled "?$+$?" and "?$-$?". The sign of a cycle is the product of its edge signs. 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)|}$?.

Rights

URN

URN:NBN:SI:DOC-FLBNZGZF

COBISSID

18822745

Added

29.05.2020

Metadata

Citation

APA:

Schaefer, Alex, Zaslavsky, Thomas (2019). The dimension of the negative cycle vectors of a signed graph. Ars mathematica contemporanea, volume 16, issue 2, str. 625-639. URN:NBN:SI:DOC-FLBNZGZF from http://www.dlib.si

MLA:

Schaefer, Alex, Zaslavsky, Thomas. "The dimension of the negative cycle vectors of a signed graph." Ars mathematica contemporanea volume 16. issue 2 (2019) str. 625-639.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-FLBNZGZF>

Ars mathematica contemporanea
2008-
(Assembly record)