Welcome to the Degree-4 census. This site will provide information about edge-transitive graphs of degree 4. This fourth edition shows graphs of up to 512 vertices. We have chosen a limit of 512 vertices to reach and include Bouwer's generalization of the Gray Graph, and we invite your comments and contributions.
The main part of the census is the Table . This is a list of all graphs in the census, telling the name, the size of the symmetry group, girth, diameter and other information. Each line has a link to an individual page for that graph, with more information about the graph. A spreadsheet version of the Table is available, and a MAGMA version of the Census itself is also available. In either form, the Table is the place to browse for graphs of a certain Order.
Notation, definitions, vocabulary can be found in the Glossary . The Glossary is the textbook of the Census and contains all the careful descriptions of the graphs. This is not a paper Glossary, so use your browser's search function. If you meet a graph in the Table called "SDD(DG(F32))", and have no idea what that means, go to the Glossary and search for SDD, for DG and for F to find out. The Glossary also explains what notations on the summary pages tells you. Look in the Glossary to find out what Ivanov vectors or cyclic coverings are.
Summaries of the contributions of individual constructions is available at Families . Here, every construction of each graph is listed. Search for, say, "MSY" to find all of the Marušič - Šparl Y-graphs and all things constructed from them. Search for "*-MSY" to see just the MSY's themselves. The search can show all the ways each of these graphs is constructed and help us understand the ways in which different graphs are related.
Completeness:The word 'Census' usually refers to a complete listing. That is very nearly true of this census. There are three kinds of edge-transitive tetravalent graphs, namely: dart-transitive, half-arc-transitive and semisymmetric. This Census inherits completeness in the first two categories from studies by Potočnik, Spiga and Verret. The third category is not known to be complete and we strongly suspect that it is not. (See the Glossary for definitions and the Recipes paper for references)
The Census is joint work of Steve Wilson at Northern Arizona University, and Primož Potočnik University of Ljubljana, Faculty of Mathematics and Physics
Acknowledgements:
First, great credit is due to John Cannon and all the team at MAGMA. Every step of the research for this tome was done with hand-holding from MAGMA. The html code for the pages of the site itself was produced (98% of it) by a MAGMA program on monsoon, NAU's computer cluster. Many thanks also go to Christopher Coffey, who wrote the grant enabling NAU to get Magma, and who has been patient and competent in answering questions.
Thanks to Marston Conder for providing us with the census of symmetric and semisymmetric 3-valent graphs!
Many thanks to Alen Orbanič for making available his census of rotary maps with up to 500 edges. We incorporated this catalogue and resulting graphs into this Census; their inclusion give explanations to many previous Mysteries. We later incorporated the larger census of maps due to Primož Potočnik, explaining even more mysteries.
And a sharp-eye award to Rui Duarte for noticing we hadn't included the third family of toroidal maps. (We now have.)
A great deal of credit is due to Gabriel Verret for writing the very elegant program which enables us to find all BGCG dissections. We also thank him for his many incisive comments and critiques. The Census is better for all the times we heeded his advice.
As the the previous editions have changed, the order in which the graphs appear in the Census (and, so, their tags) have changed a bit. This edition of the Census was created using a significantly different search system to accommodate its size. At this stage, we commit to these tags for the graphs in the Census. Thus, if we find a new graph at 136 vertices some time after 1 September 2016, we will add it to the end of the list of graphs with 136 vertices, and not re-arrange the existing ones. We promise.
Updates:
20 June 2005: Posted C4Site for the first time. It has graphs of up to 100 vertices.
8 August 2005: Included consistent cycle information.
25 August 2005: Included generalized Ivanov vectors.
23 January 2008: Included the third torus family, the LR structures RC and SoP, and the first glimmerings of the BGCG not-yet-Construction. Expanded the Census to graphs of order 150.
4 March 2008: Included BW graphs and semi-regular actions.
14 April 2008: Included DG, HC, MSY, MSX, GPS2 graphs. Added Cyclic Coverings from semi-regular actions. Check this out in the Glossary first!
21 April 2008: Modified the description and implementation of BW graphs following a suggestion by Tomaž Pisanski, causing us to re-name them the Propellor graphs, Pn(a, b, c,d). We corrrected a programming flaw in the BC graphs.
24 October 2014: Lots of material: We have finally expanded to our proposed limit of 512 vertices and have added the Brouwer-Gray graph under the name Gray(4). We have added Praeger & Gardiner's graph C+-1 and C+-e under the names CPM1 and CPME, and have then generalized these to the family CPM. We have streamlined the MSY graphs according to research by Iva Antončič. We have added a construction on cubic graphs, the "3-arc graph", abbreviated here as TAG. We have revised the search for semi-regular symmetries to eliminate duplicate diagrams. On each graph's page of related graphs we show graphs which it covers as well as those which cover it.
16 August 2016: This is, perhaps, the 'final' form of the Census. The main new things added relate to the BGCG construction: we have finally inculded those in which the Connection Graph is a cycle (though perhaps not all of those), and we now have on the 'related graphs' page for each graph its BGCG dissections and graph using the given one as the Base Graph in a BGCG construction.