Konstrukcije in katalogizacija simetričnih grafov : doktorska disertacija

Berčič, Katja (author), Potočnik, Primož (mentor)

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$.

• Language: Slovenian
• Keywords: ločno tranzitiven graf, ločno tranzitiven digraf, ločno regularen digraf, graf stopnje 4, digraf stopnje 2
• Work type: Doctoral dissertation
• Typology: 2.08 - Doctoral Dissertation
• Organization: FMF - Faculty of Mathematics and Physics
• Place of publishing: Ljubljana
• Publisher: [K. Berčič]
• Year: 2015
• Number of pages: XII, 81 str.
• PID: 20.500.12556/RUL-95859
• UDC: 519.17(043.3)
• COBISS.SI-ID: 17311321
• Publication date in RUL: 24.10.2017

BERČIČ, Katja, 2015, Konstrukcije in katalogizacija simetričnih grafov : doktorska disertacija [online]. Doctoral dissertation. Ljubljana : K. Berčič. [Accessed 9 April 2025]. Retrieved from: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=eng&id=95859

Secondary language

• Language: English

Abstract

Classification of symmetric graphs is an extensive project started in the sixties. Since then, many articles have been published on this topic and the area is still very much active. Much of the research has been dedicated to cubic symmetric graphs, including the first census of symmetric graphs, known as the Foster census. Recently, researchers have been focusing on tetravalent graphs. In this disertation we will study tetravalent arc-transitive graphs with a simple prime factorization of the order and related digraphs of valency $2$. We frame them in the wider context of symmetric graphs and present some known results. Since classifications appear in different forms in the literature, with varied notations for certain families and graphs, we put some effort into a consistent notation, which we then use in the overview of existent classificatons of arc-transitive and $1/2$-arc-transitive tetravalent graphs. We dedicate a whole chapter to two tools commonly used in classification of symmetric graphs. First, we define covers and quotients for graphs and digraphs and present some useful results. Then we summarize the theory of alter-relations and alter-exponents, to be used later in proving our result about digraphs. As an example of the quotient method with semisimple groups we then finish the clasification of tetravalent arc-transitive graphs and order $2pq$ (for distinct primes $p$ and $q$), which until know existed only for arc-regular graphs. In the following chapter we take advantage of the theory of alter-relations and alter-exponents to prove a classifications of arc-transitive digraphs of valency $2$ of orders with a certains prime factorization. The last chapter is a contribution to the census of digraphs of valency $2$.

• Keywords: arc-transitive graph, arc-transitive digraph, arc-regular digraph, 4-valent graph, 2-valent digraph, Grafi, Disertacije, Konstrukcije, Katalogizacija