Algebraic Aspects of Graph Theory

The thesis contains number of different topics in algebraic graph theory, touching and resolving some open problems that have been a center of research interest over the last decade or so. More precisely, the following open problems are considered in the thesis:

(i) Which graphs are (strongly) quasi $m$-Cayley graphs?
(ii) Which bicirculants are arc-transitive graphs?
(iii) Are there generalized Cayley graphs which are not Cayley graphs, but are vertex-transitive?
(iv) Are there snarks amongst Cayley graphs?
(v) Are there graphs admitting half-arc-transitive group actions with small number of alternets with respect to which they are not tightly attached?

Problem (i) is solved for circulants and $m\in \{2,3,4\}$. Problem (ii) is completely solved for pentavalent bicirculants. Problem (iii) is answered in the affirmative by constructing two infinite families of vertex-transitive non-Cayley generalized Cayley graphs. The graphs in the families are all bicirculants. Problem (iv) is solved for those $(2,s,t)$-Cayley graphs whose corresponding $2t$-gonal graphs are prime-valent arc-transitive bicirculants. The main step in obtaining this solution is the proof that the chromatic number of any prime-valent arc-transitive bicirculant admitting a subgroup of automorphisms acting $1$-regularly, with the exception of the complete graph $K_4$, is at most $3$. Problem (v) is solved for graphs admitting half-arc-transitive group actions with less than six alternets by showing that there exist graphs admitting half-arc-transitive group actions with four or five alternets with respect to which they are not tightly attached, whereas graphs admitting half-arc-transitive group actions with less that four alternets are all tightly attached with respect to such actions.

The thesis is prepared under supervision of Prof. Dragan Marušič and co-supervison of Assoc. Prof. Klavdija Kutnar.