Konstrukcije in katalogizacija simetričnih grafovBerčič, Katja (Avtor) Potočnik, Primož (Mentor) ločno tranzitiven grafločno tranzitiven digrafločno regularen digrafgraf stopnje 4digraf stopnje 2Klasifikacija 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$▫.[K. Berčič]20152017-09-22 02:53:59Doktorsko delo/naloga95859UDK: 519.17(043.3)COBISS_ID: 17311321sl