Predznačeni graf je graf ?$\Gamma$?, katerega povezave so označene s "?$+$?" in "?$-$?". Predznak cikla je produkt predznakov njegovih povezav. Naj ?$\mathrm{SpecC}(\Gamma)$? označuje seznam dolžin ciklov v grafu ?$\Gamma$?. Vsakemu predznačenemu grafu priredimo vektor, katerega komponente so števila negativnih ?$k$?-ciklov za ?$k \in \mathrm{SpecC}(\Gamma)$?. Ti vektorji generirajo podprostor prostora ?$\mathbb{R}^{|\mathrm{SpecC}(\Gamma)|}$?. Z uporabo prirejanj s krepko permutabilnostno lastnostjo dobimo spodnje meje za dimenzijo tega prostora in pokažemo, da je za polne grafe, polne dvodelne grafe in še nekaj drugih grafov ta prostor enak celotnemu prostoru ?$\mathbb{R}^{|\mathrm{SpecC}(\Gamma)|}$?.

Pravice

URN

URN:NBN:SI:DOC-FLBNZGZF

COBISSID

18822745

Objavljeno

29.05.2020

Metapodatki

Citiranje

APA:

Schaefer, Alex, Zaslavsky, Thomas (2019). The dimension of the negative cycle vectors of a signed graph. Ars mathematica contemporanea, letnik 16, številka 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 letnik 16. številka 2 (2019) str. 625-639.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-FLBNZGZF>

Ars mathematica contemporanea
2008-
(Zbirni zapis)