Štefko Miklavič (Author), Primož Potočnik (Author), Stephen Wilson (Author)

Abstract

A cycle decomposition of a graph ▫$\Gamma$▫ is a set ▫$\mathcal{C}$▫ of cycles of ▫$\Gamma$▫ such that every edge of ▫$\Gamma$▫ belongs to exactly one cycle in ▫$\mathcal{C}$▫. Such a decomposition is called arc-transitive if the group of automorphisms of ▫$\Gamma$▫ that preserve setwise acts transitively on the arcs of ▫$\Gamma$▫. In this paper, we study arc-transitive cycle decompositions of tetravalent graphs. In particular, we are interested in determining and enumerating arc-transitive cycle decompositions admitted by a given arc-transitive tetravalent graph. Among other results we show that a connected tetravalent arc-transitive graph is either 2-arc-transitive, or is isomorphic to the medial graph of a reflexible map, or admits exactly one cycle structure.

Keywords

matematika;teorija grafov;dekompozicija ciklov;grupa avtomorfizmov;mathematics;graph theory;cycle decomposition;automorphism group;consistent cycle;medial maps;

Data

Language: English
Year of publishing:
Typology: 1.01 - Original Scientific Article
Organization: UL FMF - Faculty of Mathematics and Physics
UDC: 519.17
COBISS: 14627417 Link will open in a new window
ISSN: 0095-8956
Views: 1
Downloads: 1
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: Slovenian
Secondary keywords: matematika;teorija grafov;dekompozicija ciklov;grupa avtomorfizmov;
Type (COBISS): Not categorized
Pages: str. 1181-1192
Volume: Vol. 98
Issue: no. 6
Chronology: 2008
DOI: 10.1016/j.jctb.2008.01.005
ID: 1473513