Math & Computer Science
Permanent URI for this community
Browse
Browsing Math & Computer Science by Subject "Automorphism"
Now showing 1 - 7 of 7
Results Per Page
Sort Options
- ItemAutomorphism groups of wreath product digraphs(Electronic Journal of Combinatorics, 2009) Dobson, Edward; Morris, JoyWe generalize a classical result of Sabidussi that was improved by Hemminger, to the case of directed color graphs. The original results give a necessary and sufficient condition on two graphs, C and D, for the automorphsim group of the wreath product of the graphs, Aut(C o D) to be the wreath product of the automorphism groups Aut(C) o Aut(D). Their characterization generalizes directly to the case of color graphs, but we show that there are additional exceptional cases in which either C or D is an infinite directed graph. Also, we determine what Aut(C o D) is if Aut(C o D) 6= Aut(C) o Aut(D), and in particular, show that in this case there exist vertex-transitive graphs C0 and D0 such that C0 oD0 = C oD and Aut(C oD) = Aut(C0) o Aut(D0).
- ItemAutomorphisms of circulants that respect partitions(University of Calgary, Department of Mathematics & Statistics, 2016) Morris, JoyIn this paper, we begin by partitioning the edge (or arc) set of a circulant (di)graph according to which generator in the connection set leads to each edge. We then further refine the partition by subdividing any part that corresponds to an element of order less than n, according to which of the cycles generated by that element the edge is in. It is known that if the (di)graph is connected and has no multiple edges, then any automorphism that respects the first partition and fixes the vertex corresponding to the group identity must be an automorphism of the group (this is in fact true in the more general context of Cayley graphs). We show that automorphisms that respect the second partition and fix 0 must also respect the first partition, and so are again precisely the group automorphisms of Zn.
- ItemAutomorphisms of the canonical double cover of a toroidal grid(University of Primorska, 2023) Morris, Dave W.The Cartesian product of two cycles (of length m and length n) has a natural embedding on the torus, such that each face of the embedding is a 4-cycle. The toroidal grid Qd(m,n,r) is a generalization of this in which there is a shift by r when traversing the meridian of length m. In 2008, Steve Wilson found two interesting infinite families of (nonbipartite) toroidal grids that are unstable. (By definition, this means that the canonical bipartite double cover of the grid has more than twice as many automorphisms as the grid has.) It is easy to see that bipartite grids are also unstable, because the canonical double cover is disconnected. Furthermore, there are degenerate cases in which there exist two different vertices that have the same neighbours. This paper proves Wilson's conjecture that Qd(m,n,r) is stable for all other values of the parameters. In addition, we prove an analogous conjecture of Wilson for the triangular grids Tr(m,n,r) that are obtained by adding a diagonal to each face of Qd(m,n,r) (with all of the added diagonals parallel to each other).
- ItemDigraphs with small automorphism groups that are Cayley on two nonisomorphic groups(University of Primorska, 2020) Morgan, Luke; Morris, Joy; Verret, GabrielLet Γ = Cay(G, S) be a Cayley digraph on a group G and let A = Aut(Γ). The Cayley index of Γ is |A : G|. It has previously been shown that, if p is a prime, G is a cyclic p-group and A contains a noncyclic regular subgroup, then the Cayley index of Γ is superexponential in p. We present evidence suggesting that cyclic groups are exceptional in this respect. Specifically, we establish the contrasting result that, if p is an odd prime and G is abelian but not cyclic, and has order a power of p at least p3, then there is a Cayley digraph Γ on G whose Cayley index is just p, and whose automorphism group contains a nonabelian regular subgroup.
- ItemOn colour-preserving automorphisms of Caley graphs(Drustvo Matematikov, Fizikov in Astronomov, 2016) Hujdurovic, Ademir; Kutnar, Klavdija; Morris, Dave W.; Morris, JoyWe study the automorphisms of a Cayley graph that preserve its natural edge-colouring. More precisely, we are interested in groups G, such that every such automorphism of every connected Cayley graph on G has a very simple form: the composition of a left-translation and a group automorphism. We find classes of groups that have the property, and we determine the orders of all groups that do not have the property. We also have analogous results for automorphisms that permute the colours, rather than preserving them.
- ItemToida's conjecture is true(Electronic Journal of Combinatorics, 2002) Dobson, Edward; Morris, JoyLet S be a subset of the units in Zn. Let Γ be a circulant graph of order n (a Cayley graph of Zn) such that if ij ∈ E(Γ), then i − j (mod n) ∈ S. Toida conjectured that if Γ0 is another circulant graph of order n, then Γ and Γ 0 are isomorphic if and only if they are isomorphic by a group automorphism of Zn. In this paper, we prove that Toida’s conjecture is true. We further prove that Toida’s conjecture implies Zibin’s conjecture, a generalization of Toida’s conjecture.
- ItemVertex-transitive digraphs with extra automorphisms that preserve the natural arc-colouring(The University of Queensland, Centre for Discrete Mathematics and Computing, 2017) Dobson, Ted; Hujdurovic, Ademir; Kutnar, Klavdija; Morris, JoyIn a Cayley digraph on a group G, if a distinct colour is assigned to each arc-orbit under the left-regular action of G, it is not hard to show that the elements of the left-regular action of G are the only digraph automorphisms that preserve this colouring. In this paper, we show that the equivalent statement is not true in the most straightforward generalisation to G-vertex-transitive digraphs, even if we restrict the situation to avoid some obvious potential problems. Specifically, we display an infinite family of 2-closed groups G, and a G-arc-transitive digraph on each (without any digons) for which there exists an automorphism of the digraph that is not an element of G (it is an automorphism of G). Since the digraph is G-arc-transitive, the arcs would all be assigned the same colour under the colouring by arc-orbits, so this digraph automorphism is colour-preserving.