| Title: | Vertex-transitive expansions of (1, 3)-trees |
|---|
| Authors: | ID Lovrečič Saražin, Marko (Author)
ID Marušič, Dragan (Author) |
|---|
| Files: |  http://dx.doi.org/10.1016/j.disc.2009.11.036
|
|---|
| Language: | English |
|---|
| Work type: | Not categorized |
|---|
| Typology: | 1.08 - Published Scientific Conference Contribution |
|---|
| Organization: | IAM - Andrej Marušič Institute
|
|---|
| 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 ▫$X$▫ with a semiregular automorphism ▫$\gamma$▫, the quotient of ▫$X$▫ relative to ▫$\gamma$▫ is the multigraph ▫$X/\gamma$▫ whose vertices are the orbits of ▫$\gamma$▫ and two vertices are adjacent by an edge with multiplicity ▫$r$▫ if every vertex of one orbit is adjacent to ▫$r$▫ vertices of the other orbit. We say that ▫$X$▫ is an expansion of ▫$X/\gamma$▫. In [J.D. Horton, I.Z. Bouwer, Symmetric ▫$Y$▫-graphs and ▫$H$▫-graphs, J. Combin. Theory Ser. B 53 (1991) 114-129], Hortonand Bouwer considered a restricted sort of expansions (which we will call :strong" in this paper) where every leaf of ▫$X/\gamma$▫ expands to a single cycle in ▫$X$▫. They determined all cubic arc-transitive strong expansions of simple ▫$(1,3)$▫-trees, that is, trees with all of their vertice shaving 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 ▫$K_2$▫ (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. |
|---|
| Keywords: | graph, tree, cubic, vertex-transitive, arc-transitive, expansion |
|---|
| Year of publishing: | 2010 |
|---|
| Number of pages: | str. 1772-1782 |
|---|
| Numbering: | Vol. 310, no. 12 |
|---|
| PID: | 20.500.12556/RUP-7  |
|---|
| ISSN: | 0012-365X |
|---|
| UDC: | 519.17 |
|---|
| COBISS.SI-ID: | 1024192340 |
|---|
| Publication date in RUP: | 15.10.2013 |
|---|
| Views: | 4441 |
|---|
| Downloads: | 81 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
