Faculty Research and Publications

Permanent URI for this community

https://opus.uleth.ca/handle/10133/4940

Browse

Now showing 1 - 9 of 9

Automorphism groups of wreath product digraphs
(Electronic Journal of Combinatorics, 2009) Dobson, Edward; Morris, Joy
We 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 suﬃcient 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 inﬁnite 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).
Automorphisms of circulants that respect partitions
(University of Calgary, Department of Mathematics & Statistics, 2016) Morris, Joy
In 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 reﬁne 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 ﬁrst partition and ﬁxes 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 ﬁx 0 must also respect the ﬁrst partition, and so are again precisely the group automorphisms of Zn.
Characterising CCA Sylow cyclic groups whose order is not divisible by four
(Drustvo Matematikov, Fizikov in Astronomov, 2018) Morgan, Luke; Morris, Joy; Verret, Gabriel
A Cayley graph on a group G has a natural edge-colouring. We say that such a graph is CCA if every automorphism of the graph that preserves this edge-colouring is an element of the normaliser of the regular representation of G. A group G is then said to be CCA if every connected Cayley graph on G is CCA. Our main result is a characterisation of non-CCA graphs on groups that are Sylow cyclic and whose order is not divisible by four. We also provide several new constructions of non-CCA graphs.
On colour-preserving automorphisms of Caley graphs
(Drustvo Matematikov, Fizikov in Astronomov, 2016) Hujdurovic, Ademir; Kutnar, Klavdija; Morris, Dave Witte; Morris, Joy
We 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 ﬁnd 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.
On the automorphism groups of almost all circulant graphs and digraphs
(Drustvo Matematikov, Fizikov in Astronomov, 2018) Bhoumik, Soumya; Dobson, Edward; Morris, Joy
We attempt to determine the structure of the automorphism group of a generic circulant graph. We ﬁrst show that almost all circulant graphs have automorphism groups as small as possible. The second author has conjectured that almost all of the remaining circulant (di)graphs (those whose automorphism group is not as small as possible) are normal circulant (di)graphs. We show this conjecture is not true in general, but is true if we consider only those circulant (di)graphs whose order is in a “large” subset of integers. We note that all non-normal circulant (di)graphs can be classiﬁed into two natural classes (generalized wreath products, and deleted wreath type), and show that neither of these classes contains almost every non-normal circulant digraph.
Semiregular automorphisms of cubic vertex-transitive graphs and the abelian normal quotient method
(Electronic Journal of Combinatorics, 2015) Morris, Joy; Spiga, Pablo; Verret, Gabriel
We characterise connected cubic graphs admitting a vertex-transitive group of automorphisms with an abelian normal subgroup that is not semiregular. We illustrate the utility of this result by using it to prove that the order of a semiregular subgroup of maximum order in a vertex-transitive group of automorphisms of a connected cubic graph grows with the order of the graph.
Strongly regular edge-transitive graphs
(Drustvo Matematikov, Fizikov in Astronomov, 2009) Morris, Joy; Praeger, Cheryl E.; Spiga, Pablo
In this paper, we examine the structure of vertex- and edge-transitive strongly regular graphs,using normal quotient reduction. We show that their reducible graphs in this family have quasi primitive automorphism groups, and prove (using the Classiﬁcation of Finite Simple Groups) that no graph in this family has a holomorphic simple automorphism group. We also ﬁnd some constraints on the parameters of the graphs in this family that reduce to complete graphs
Toida's conjecture is true
(Electronic Journal of Combinatorics, 2002) Dobson, Edward; Morris, Joy
Let 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.
Vertex-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, Joy
In 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. Speciﬁcally, we display an inﬁnite 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.