Published in

Elsevier, Discrete Mathematics, 12(310), p. 1772-1782, 2010

DOI: 10.1016/j.disc.2009.11.036

Links

Tools

Export citation

Search in Google Scholar

Vertex-transitive expansions of (1, 3)-trees

Journal article published in 2010 by Marko Lovrečič Saražin, Dragan Marušič
This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Green circle
Preprint: archiving allowed
Orange circle
Postprint: archiving restricted
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

A nonidentity automorphism of a graph is said to be semiregular if all of its orbits are of the same length. Given a graph XX with a semiregular automorphism γγ, the quotient of XX relative to γγ is the multigraph X/γX/γ whose vertices are the orbits of γγ and two vertices are adjacent by an edge with multiplicity rr if every vertex of one orbit is adjacent to rr vertices of the other orbit. We say that XX is an expansion of X/γX/γ. In [J.D. Horton, I.Z. Bouwer, Symmetric YY-graphs and HH-graphs, J. Combin. Theory Ser. B 53 (1991) 114–129], Horton and Bouwer considered a restricted sort of expansions (which we will call ‘strong’ in this paper) where every leaf of X/γX/γ expands to a single cycle in XX. They determined all cubic arc-transitive strong expansions of simple (1, 3)-trees, that is, trees with all of their vertices having valency 1 or 3, thus extending the classical result of Frucht, Graver and Watkins (see [R. Frucht, J.E. Graver, M.E. Watkins, The groups of the generalized Petersen graphs, Proc. Cambridge Philos. Soc. 70 (1971) 211–218]) about arc-transitive strong expansions of K2K2 (also known as the generalized Petersen graphs). In this paper another step is taken further by considering the possible structure of cubic vertex-transitive expansions of general (1,3)-multitrees (where vertices with double edges are also allowed); thus the restriction on every leaf to be expanded to a single cycle is dropped.