Search

Let ${\cal M}$ be a map with the underlying graph $\Gamma$. The automorphism group $Aut({\cal M})$ induces a natural action on the set of all vertex-edge-face incident triples, called {\em flags} of ${\cal M}$. The map ${\cal M}$ is said to be a {\em $k$-orbit} map if $Aut({\cal M})$ has $k$ orbits on the set of all flags of ${\cal M}$. It is known that there are seven different classes of $2$-orbit maps, with only four of them corresponding to arc-transitive maps, that is maps for which $Aut{\cal M}$ acts arc-transitively on the underlying graph $\Gamma$. The Petrie dual operator links these four classes in two pairs, one of which corresponds to the chiral maps and their Petrie duals. In this paper we focus on the other pair of classes of $2$-orbit arc-transitive maps. We investigate the connection of these maps to consistent cycles of the underlying graph with special emphasis on such maps of smallest possible valence, namely $4$. We then give a complete classification of such maps whose underlying graphs are arc-transitive Rose Window graphs.

Let m > n ≥ 2 and g ≥ 4 be positive integers. A graph G is called a bipartite ( m , n ; g ) -graph if it is a biregular bipartite graph of even girth g with the additional property that all vertices in each of the two partition sets are of the same degree; m in one of them, and n in the other. In analogy with the well-known Cage Problem, if we let v ( G ) denote the order of G , and let B ( m , n ; g ) denote the natural lower bound for the order of bipartite ( m , n ; g ) -graphs obtained as a generalization of the Moore bound for regular graphs, we call the difference v ( G ) − B ( m , n ; g ) the excess of G . The focus of this paper is on the study of the question of the existence of bipartite ( m , n ; g ) -graphs for given parameters ( m , n ; g ) and excess at most 4. We prove that such graphs are rare by finding restrictive necessary arithmetic conditions on the parameters m , n and g . Furthermore, we prove the non-existence of bipartite ( m , n ; g ) -graphs of excess at most 4 for all parameters m , n , g where g ≥ 10 and is not divisible by 4, and m > n ≥ 3 . In the case when the girth of G is 6, we employ spectral analysis of the distance matrices of G , and find necessary relations between their eigenvalues. Finally, we prove for all pairs m , n , m > n ≥ 3 , that the asymptotic density of the set of even girths g ≥ 8 for which there exists a bipartite ( m , n ; g ) -graph with excess not exceeding 4 is equal to 0.

A graph is said to be half-arc-transitive if its automorphism group acts transitively on its vertex set and its edge set, but not on its arc set. In 1970 I. Z. Bouwer constructed an infinite family of vertex- and edge-transitive graphs for each even valence greater than 2 and proved that a subfamily of the constructed graphs, containing one graph for each even valence greater than 2, consists of half-arc-transitive graphs. In a recent paper Conder and Žitnik gave a complete classification of the half-arc-transitive Bouwer graphs. In this paper we generalize the Bouwer graphs to obtain a much larger family of vertex- and edge-transitive graphs, containing almost all so-called tightly attached quartic half-arc-transitive graphs. We give a complete classification of the half-arc-transitive members of this new family of graphs. All half-arc-transitive members are tightly attached.