Some statistics on small connected trivalent vertex-transitive graphs (Seminar DM)

Iz MaFiRaWiki

Some statistics on small connected trivalent vertex-transitive graphs

Tomaž Pisanski

Torek, 21. oktobra 2014, od 10h do 12h, Plemljev seminar, Jadranska 19

Povzetek: In April 2014 Primož Potočnik, Pablo Spiga and Gabriel Verret last updated a census of small connected cubic vertex-transitive graphs: The census contains 111360 graphs of order at most 1280 and is spread over 13 files, the largest having 234 MB. It was shown by Marušič and Scapellato [1] that every trivalent vertex-transitive graph has a semi-regular automorphism.

This enabled us to represent each graph from the census as a cyclic cover over a smaller graph. Using this fact we are able to represent the graphs stored in the census files to a single file of size about 2 % of the original size. In this talk some statistics that complement the statistics from [2] and [3] will be presented. Most of the talk is work in progress with Robert Morse and Primož Potočnik. This is an update of a talk given in Novosibirsk.


  1. D. Marušič, R. Scapellato, Permutation groups, vertex-transitive digraphs and semiregular automorphisms. European J. Combin. 19 (1998), no. 6, 707-712.
  2. P. Potočnik, P. Spiga, G. Verret, Cubic vertex-transitive graphs on up to 1280 vertices, arXiv:1201.5317v1 [math.CO].
  3. P. Potočnik, P. Spiga, G. Verret, Bounding the order of the vertex-stabiliser in 3-valent vertex-transitive and 4-valent arc-transitive graphs, arXiv:1010.2546v1 [math.CO].

Glej tudi/See also

Seminar za diskretno matematiko

Osebna orodja