This MSc thesis deals with certain topics from algebraic graph theory. In this field of mathematics, we usually study so-called graph automorphisms (also called symmetries), which are permutations of the graph's vertex set, perserving adjacency. Quite often, the goal is to classify all of the graphs with chosen symmetry properties. There exist graphs, which are symmetric enough, so that their automorphism group acts transitively on their vertex set. This means that for any pair of vertices of the graph there is an automorphism, mapping one vertex to the other. Such graphs are called vertex-transitive. Similarly, a graph is edge-transitive, if its automorphism group acts transitively on its edge set and is arc-transitive if its automorphism group acts transitively on its arc set.
A bicirculant is a graph, admitting an automorphism with two orbits of the same length. Frucht, Graver and Watkins were the first to systematically study symmetries of Generalized Petersen Graphs (1971) and classifing all vertex and edge-transitive ones. In this way they began the study of symmetries of bicirculants. The next step was done by Wilson in 2008, who made an important step towards the classification of edge-transitive Rose-Window graphs by identifying four families of such graphs. His work was completed two years later by Kovács, Kutnar and Marušič. Similarly, Arroyo, Hubard, Kutnar, O'Reilly and Šparl classified all arc-transitive Tabačjn graphs in 2015.
In this thesis, we introduce 6-valent generalization of Generalized Petersen graphs. The chosen family of graphs was not a subject of any research until now. We name the corresponding graphs as Nest graphs. The main goal of the thesis is to start a classification of symmetric Nest graphs, where we make a few first, but, nonetheless, important steps. We firstly present the family of Nest graphs, along with some of their basic properties and facts about them, where we focus on their symmetry properties. Based on the results, obtained with the aid of the computer package Magma, we then identify some families of symmetric Nest graphs and for each of their members prove that they indeed are symmetric Nest graphs. One of the key results of the thesis is also an almost completed classification of symmetric Nest graphs of girth 3.