Konstrukcije in katalogizacija simetričnih grafov : doktorska disertacija

slovenski

doktorska dela

2015

2-valent digraph   4-valent graph   arc-regular digraph   arc-transitive digraph   arc-transitive graph   digraf stopnje 2   Disertacije   graf stopnje 4   Grafi   Katalogizacija   Konstrukcije   ločno regularen digraf   ločno tranzitiven digraf   ločno tranzitiven graf

Univerza v Ljubljani, Fakulteta za matematiko in fiziko
(Obvezni izvod spletne publikacije)

Klasifikacija simetričnih grafov je obsežno delo, ki se je začelo v šestdesetih letih prejšnjega stoletja. Od takrat je bilo na to temo napisanih veliko člankov, področje pa je še vedno aktivno. Največ je bilo narejenega na temo simetričnih grafov stopnje ?$3$?, vključno s prvim katalogom simetričnih grafov, ki ga poznamo pod imenom Fosterjev cenzus. Fokus raziskovanja se je v zadnjem času premaknil na področje grafov stopnje ?$4$?. V disertaciji preučujemo ločno tranzitivne grafe stopnje ?$4$? in z njimi povezane digrafe stopnje ?$2$?, katerih red ima preprost praštevilski razcep. Postavimo jih v širši okvir simetričnih grafov in predstavimo znane rezultate. V literaturi se klasifikacije pojavljajo v različnih oblikah, nekatere družine grafov in posamezni grafi pa pod raznovrstnimi oznakami, zato v prvem poglavju pregledamo znane klasifikacije ločno tranzitivnih in ?$1/2$?-ločno tranzitivnih grafov stopnje ?$4$? in jih zapišemo v enotnem jeziku. Eno poglavje je v celoti namenjeno predstavitvi dveh pripomočkov pri klasificiranju simetričnih grafov. V prvem delu zapišemo definicije krovov in kvocientov za grafe in digrafe, skupaj z nekaj priročnimi rezultati. Preostanek je namenjen povzetku teorije o izmeničnih ciklih in alter-eksponentih, ki jo s pridom uporabimo v dokazu izreka za digrafe. Kot zgled uporabe kvocientne metode s polenostavnimi grupami nato dokončamo klasifikacijo ločno tranzitivnih grafov stopnje ?$4$? in reda ?$2pq$? (za različni lihi praštevili ?$p$? in ?$q$?), ki je bila do sedaj narejena le za ločno regularne grafe. V naslednjem poglavju s pridom uporabimo teorijo izmeničnih ciklov, da dokažemo klasifikacijo ločno tranzitivnih digrafov stopnje ?$2$? nekaterih redov s predpisanim praštevilskim razcepom. Zadnje poglavje je prispevek h katalogu digrafov stopnje ?$2$?.

12.05.2023