Primitive, edge-short, isometric, and pantochordal cycles

angleški

2025

letnik 8, številka 2, article p2.01

blokovski graf   geodetski cikli   Hamiltonovi cikli   kografi   polni večdelni graf   povezavno kratek cikel   tetiva

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Cikel v grafu G je primitiven za svojo točko x, če najmanj ena njegovih povezav ne pripada nobenemu krajšemu ciklu, ki gre skozi x. Tovrstni cikel in z njim povezan pojem razširjenih okolic igrata ključno vlogo v algoritmih za posredovanje sporočil, ki izračunavajo spektralne lastnosti grafov s kratkimi zankami. Tukaj raziskujemo takšne primitivne cikle in grafe brez dolgih primitivnih ciklov v tradicionalnejšem okviru teorije grafov. Pokažemo, da je cikel primitiven za vse svoje točke natanko takrat, ko je izometričen. Cikel imenujemo popolnoma redundanten, če ni primitiven za nobeno svojo točko, in pokažemo, da popolnoma redundantni cikli niso povezavno kratki, to pomeni, da se jih ne da predstaviti kot povezavno disjunktno unijo ene same povezave in dveh krajših poti v grafu G. Družini Rk in Lk grafov z vsemi cikli dolžine najmanj k+1, ki so popolnoma redundantni oz. niso povezavno kratki, sovpadata za k=3 in k=4. V teh grafih so vsi cikli dolžine najmanj k+1 pantokordalni, kar pomeni, da je vsaka od točk incidentna neki tetivi. Noben od teh rezultatov se ne posploši na k?5. Poleg tega se je izkazalo, da so R3=L3 blokovski grafi, in da so R4=L4 grafi s popolnimi večdelnimi bloki. Nazadnje pokažemo, da kografi tvorijo pravo podmnožico družine R5.

08.09.2026