Vertex-transitive graphs and their arc-types

english

2017

volume 12, issue 2

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Let ?$X$? be a finite vertex-transitive graph of valency ?$d$?, and let ?$A$? be the full automorphism group of ?$X$?. Then the arc-type of ?$X$? is defined in terms of the sizes of the orbits of the stabiliser ?$A_v$? of a given vertex ?$v$? on the set of arcs incident with ?$v$?. Such an orbit is said to be self-paired if it is contained in an orbit ?$\Delta$? of ?$A$? on the set of all arcs of v$X$? such that v$\Delta$? is closed under arc-reversal. The arc-type of ?$X$? is then the partition of ?$d$? as the sum ?$n_1 + n_2 + \dots + n_t + (m_1 + m_1) + (m_2 + m_2) + \dots + (m_s + m_s)$?, where ?$n_1, n_2, \dots, n_t$? are the sizes of the self-paired orbits, and ?$m_1,m_1, m_2,m_2, \dots, m_s,m_s$? are the sizes of the non-self-paired orbits, in descending order. In this paper, we find the arc-types of several families of graphs. Also we show that the arc-type of a Cartesian product of two "relatively prime" graphs is the natural sum of their arc-types. Then using these observations, we show that with the exception of ?$1+1$? and ?$(1+1)$?, every partition as defined above is \emph{realisable}, in the sense that there exists at least one vertex-transitive graph with the given partition as its arc-type.

29.05.2020