Konstrukcije in katalogizacija simetričnih grafov - Berčič, Katja (visokošolska dela, 2015)
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: 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