Vertex-transitive graphs and their arc-types - Conder, Marston D. E. (Ars mathematica contemporanea, 2017)
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 ?$Δ$? of ?$A$? on the set of all arcs of v$X$? such that v$Δ$? is closed under arc-reversal. The arc-type of ?$X$? is then the partition of ?$d$? as the sum ?$n_1 + n_2 + … + n_t + (m_1 + m_1) + (m_2 + m_2) + … + (m_s + m_s)$?, where ?$n_1, n_2, …, n_t$? are the sizes of the self-paired orbits, and ?$m_1,m_1, m_2,m_2, …, 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 realisable, in the sense that there exists at least one vertex-transitive graph with the given partition as its arc-type.
Keywords: Cayleyjev graf; kartezični produkt; krovni graf; ločno trazitiven graf; tip simetrije; vozliščno tranzitiven graf