Morris, Joy

Permanent URI for this collection

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

Browse

Browsing Morris, Joy by Subject "Cayley graph"

Now showing 1 - 5 of 5
  • Thumbnail Image
    Item
    Cayley graphs of more than one abelian group
    (University of Primorska, 2021) Dobson, Edward; Morris, Joy
    We show that for certain integers n, the problem of whether or not a Cayley digraph Γ of ℤn is also isomorphic to a Cayley digraph of some other abelian group G of order n reduces to the question of whether or not a natural subgroup of the full automorphism group contains more than one regular abelian group up to isomorphism (as opposed to the full automorphism group). A necessary and sufficient condition is then given for such circulants to be isomorphic to Cayley digraphs of more than one abelian group, and an easy-to-check necessary condition is provided.
  • Thumbnail Image
    Item
    Groups for which it is easy to detect graphical regular representations
    (University of Primorska, 2022) Morris, Dave W.; Morris, Joy; Verret, Gabriel
    We say that a finite group G is DRR-detecting if, for every subset S of G, either the Cayley digraph Cay(G,S) is a digraphical regular representation (that is, its automorphism group acts regularly on its vertex set) or there is a nontrivial group automorphism φ of G such that φ(S) = S. We show that every nilpotent DRR-detecting group is a p-group, but that the wreath product Zp wr Zp is not DRR-detecting, for every odd prime p. We also show that if G1 and G2 are nontrivial groups that admit a digraphical regular representation and either gcd(|G1|, |G2|) = 1, or G2 is not DRR-detecting, then the direct product G1 x G2 is not DRR-detecting. Some of these results also have analogues for graphical regular representations.
  • Thumbnail Image
    Item
    Most rigid representations and Cayley index
    (University of Primorska, 2018) Morris, Joy; Tymburski, Josh
    For any finite group G, a natural question to ask is the order of the smallest possible automorphism group for a Cayley graph on G. A particular Cayley graph whose automorphism group has this order is referred to as an MRR (Most Rigid Representation), and its Cayley index is a numerical indicator of this value. Study of GRRs showed that with the exception of two infinite families and thirteen individual groups, every group admits a Cayley graph whose MRR is a GRR, so that the Cayley index is 1. The full answer to the question of finding the smallest possible Cayley index for a Cayley graph on a fixed group was almost completed in previous work, but the precise answers for some finite groups and one infinite family of groups were left open. We fill in the remaining gaps to completely answer this question.
  • Thumbnail Image
    Item
    On the asymptotic enumeration of Cayley graphs
    (Springer, 2021) Morris, Joy; Moscatiello, Mariapia; Spiga, Pablo
    In this paper, we are interested in the asymptotic enumeration of Cayley graphs. It has previously been shown that almost every Cayley digraph has the smallest possible auto- morphism group: that is, it is a digraphical regular representation (DRR). In this paper, we approach the corresponding question for undirected Cayley graphs. The situation is com- plicated by the fact that there are two infinite families of groups that do not admit any graphical regular representation (GRR). The strategy for digraphs involved analysing sepa- rately the cases where the regular group R has a nontrivial proper normal subgroup N with the property that the automorphism group of the digraph fixes each N-coset setwise, and the cases where it does not. In this paper, we deal with undirected graphs in the case where the regular group has such a nontrivial proper normal subgroup.
  • Thumbnail Image
    Item
    On the automorphism groups of almost all circulant graphs and digraphs
    (University of Primorska, 2014) 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.