TY - JOUR
T1 - Tetravalent edge-transitive graphs of girth at most 4
AU - Potočnik, Primož
AU - Wilson, Steve
N1 - Funding Information:
Keywords: Graph; Automorphism group; Symmetry; Edge-transitive graphs; Tetravalent graphs; Locally arc-transitive graph; Semisymmetric graph; Cycle decomposition; Linking ring structure E-mail addresses: [email protected], [email protected] (P. Potocˇnik), [email protected] (S. Wilson). 1 Address for correspondence: Institute of Mathematics, Physics and Mechanics, Jadranska 19, SI-1000 Ljubljana, Slovenia. 2 The author gratefully acknowledges the support of the US Department of State and the Fulbright Scholar Program who sponsored his visit to Northern Arizona University in spring 2004.
PY - 2007/3
Y1 - 2007/3
N2 - This is the first in the series of articles stemming from a systematical investigation of finite edge-transitive tetravalent graphs, undertaken recently by the authors. In this article, we study a special but important case in which the girth of such graphs is at most 4. In particular, we show that, except for a single arc-transitive graph on 14 vertices, every edge-transitive tetravalent graph of girth at most 4 is the skeleton of an arc-transitive map on the torus or has one of these two properties: (1)there exist two vertices sharing the same neighbourhood,(2)every edge belongs to exactly one girth cycle. Graphs with property (1) or (2) are then studied further. It is shown that they all arise either as subdivided doubles of smaller arc-transitive tetravalent graphs, or as line graphs of triangle-free (G, 1)-regular and (G, 2)-arc-transitive cubic graphs, or as partial line graphs of certain cycle decompositions of smaller tetravalent graphs.
AB - This is the first in the series of articles stemming from a systematical investigation of finite edge-transitive tetravalent graphs, undertaken recently by the authors. In this article, we study a special but important case in which the girth of such graphs is at most 4. In particular, we show that, except for a single arc-transitive graph on 14 vertices, every edge-transitive tetravalent graph of girth at most 4 is the skeleton of an arc-transitive map on the torus or has one of these two properties: (1)there exist two vertices sharing the same neighbourhood,(2)every edge belongs to exactly one girth cycle. Graphs with property (1) or (2) are then studied further. It is shown that they all arise either as subdivided doubles of smaller arc-transitive tetravalent graphs, or as line graphs of triangle-free (G, 1)-regular and (G, 2)-arc-transitive cubic graphs, or as partial line graphs of certain cycle decompositions of smaller tetravalent graphs.
KW - Automorphism group
KW - Cycle decomposition
KW - Edge-transitive graphs
KW - Graph
KW - Linking ring structure
KW - Locally arc-transitive graph
KW - Semisymmetric graph
KW - Symmetry
KW - Tetravalent graphs
UR - http://www.scopus.com/inward/record.url?scp=33846160597&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33846160597&partnerID=8YFLogxK
U2 - 10.1016/j.jctb.2006.03.007
DO - 10.1016/j.jctb.2006.03.007
M3 - Article
AN - SCOPUS:33846160597
SN - 0095-8956
VL - 97
SP - 217
EP - 236
JO - Journal of Combinatorial Theory. Series B
JF - Journal of Combinatorial Theory. Series B
IS - 2
ER -