The arc-types of Cayley graphs

angleški

2018

letnik 15, številka 1

Cayleyjev graf   kartezični produkt   krovni graf   ločno tranzitivni graf   ničelno-simetrični graf   simetrijski tip   vozliščno tranzitivni graf

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

Naj bo ?$X$? končen vozliščno-tranzitven graf valence ?$d$?, in naj bo ?$A$? polna grupa avtomorfizmov grafa ?$X$?. Potem je ločni tip grafa ?$X$? definiran glede na velikosti orbit delovanja stabilizatorja ?$A_v$? danega vozlišča ?$v$? na množici lokov incidentnih z ?$v$?. Posebej, ločni tip je razbitje ?$d$? na vsoto ?$n_1+n_2+\cdots+n_t+(m_1+m_1) + (m_2+m_2) + \cdots + (m_s+m_s)$?, kjer so ?$n_1, n_2, \cdots, n_t$? velikosti sebi zrcalnih orbit, in ?$m_1, m_1, m_2, m_2, \cdots, m_s, m_s$? velikosti orbit sebi ne-zrcalnih orbit, v padajočem redu. V nedavnem članku so Conder, Pisanski in Žitnik pokazali, da se, z izjemo razbitij ?$1 + 1$? in ?$(1 + 1)$? z valenco 2, vsako takšno razbitje pojavlja kot ločni tip nekega vozliščno tranzitivnega grafa. V tem članku razširimo ta rezultat in pokažemo, da se vsako razbitje, različno od 1, ?$v1 + 1$? and ?$(1 + 1$)?, pojavlja kot ločni tip neskončno mnogo povezanih končnih Cayleyjevih grafov z dano valenco ?$d$?. Od tod sledi, da za vsak ?$d > 2$? obstaja neskončno mnogo ničelno-simetričnih grafov (ali GRR-ov) valence ?$d$?.

29.05.2020