Math & Computer Science

Permanent URI for this community

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

Browse

Browsing Math & Computer Science by Author "Dobson, Edward"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    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 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).
  • Thumbnail Image
    Item
    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 first 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 classified 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.
  • Thumbnail Image
    Item
    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.