Faculty Research and Publications

Permanent URI for this community

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

Browse

Browsing Faculty Research and Publications by Title

Now showing 1 - 20 of 47
  • Thumbnail Image
    Item
    Arc-disjoint hamiltonian paths in Cartesian products of directed cycles
    (University of Primorska, 2025) Darijani, Iren; Miraftab, Babak; Morris, Dave W.
    We show that if C1 and C2 are directed cycles (of length at least two), then the Cartesian product C1 □ C2 has two arc-disjoint hamiltonian paths. (This answers a question asked by J. A. Gallian in 1985.) The same conclusion also holds for the Cartesian product of any four or more directed cycles (of length at least two), but some cases remain open for the Cartesian product of three directed cycles. We also discuss the existence of arc-disjoint hamiltonian paths in 2-generated Cayley digraphs on (finite or infinite) abelian groups.
  • 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
    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 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.
  • Thumbnail Image
    Item
    Automorphisms 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).
  • Thumbnail Image
    Item
    Average liar count for degree-2 Frobenius pseudoprimes
    (American Mathematical Society, 2020) Fiori, Andrew; Shallue, Andrew
    In this paper we obtain lower and upper bounds on the average number of liars for the Quadratic Frobenius Pseudoprime Test of Grantham [Math. Comp. 70 (2001), pp. 873–891], generalizing arguments of Erdős and Pomerance [Math. Comp. 46 (1986), pp. 259–279] and Monier [Theoret. Comput. Sci. 12 (1980), 97–108]. These bounds are provided for both Jacobi symbol cases, providing evidence for the existence of several challenge pseudoprimes.
  • Thumbnail Image
    Item
    Caley graphs of order 16p are hamiltonian
    (Drustvo Matematikov, Fizikov in Astronomov, 2012) Curran, Stephen J.; Morris, Dave W.; Morris, Joy
    Suppose G is a finite group, such that |G| = 16p, where p is prime. We show that if S is any generating set of G, then there is a hamiltonian cycle in the corresponding Cayley graph Cay(G;S).
  • 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
    Cayley graphs on abelian and generalized dihedral groups
    (University of Primorska, 2023) Morris, Joy; Skelton, Adrian
    A number of authors have studied the question of when a graph can be represented as a Cayley graph on more than one nonisomorphic group. In this paper we give conditions for when a Cayley graph on an abelian group can be represented as a Cayley graph on a generalized dihedral group, and conditions for when the converse is true.
  • Thumbnail Image
    Item
    Cayley graphs on groups with commutator subgroup of order 2p are hamiltonian
    (University of Primorska, 2018) Morris, Dave W.
    We show that if G is a finite group whose commutator subgroup [G, G] has order 2p, where p is an odd prime, then every connected Cayley graph on G has a hamiltonian cycle.
  • Thumbnail Image
    Item
    Cayley graphs on nilpotent groups with cyclic commutator subgroup are hamiltonian
    (University of Primorska, 2014) Ghaderpour, Ebrahim; Morris, Dave W.
    We show that if G is any nilpotent, finite group, and the commutator subgroup of G is cyclic, then every connected Cayley graph on G has a hamiltonian cycle.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    The CI problem for infinite groups
    (Electronic Journal of Combinatorics, 2016) Morris, Joy
    A finite group G is a DCI-group if, whenever S and S0 are subsets of G with the Cayley graphs Cay(G,S) and Cay(G,S0) isomorphic, there exists an automorphism ϕ of G with ϕ(S) = S0. It is a CI-group if this condition holds under the restricted assumption that S = S−1. We extend these definitions to infinite groups, and make two closely-related definitions: an infinite group is a strongly (D)CIf-group if the same condition holds under the restricted assumption that S is finite; and an infinite group is a (D)CIf-group if the same condition holds whenever S is both finite and generates G. We prove that an infinite (D)CI-group must be a torsion group that is not locallyfinite. We find infinite families of groups that are (D)CIf-groups but not strongly (D)CIf-groups, and that are strongly (D)CIf-groups but not (D)CI-groups. We discuss which of these properties are inherited by subgroups. Finally, we completely characterise the locally-finite DCI-graphs on Zn. We suggest several open problems related to these ideas, including the question of whether or not any infinite (D)CIgroup exists.
  • Thumbnail Image
    Item
    Classification of vertex-transitive digraphs of order a product of two distinct primes via automorphism group
    (2025) Dobson, Ted; Hujdurovic, Ademir; Kutnar, Klavdija; Morris, Joy
    In the mid-1990s, two groups of authors independently obtained classifications of vertex-transitive graphs whose order is a product of two distinct primes. In the intervening years it has become clear that there is additional information concerning these graphs that would be useful, as well as making explicit the extensions of these results to digraphs. Additionally, there are several small errors in some of the papers that were involved in this classification. The purpose of this paper is to fill in the missing information as well as correct all known errors.
  • Thumbnail Image
    Item
    Cyclic m-cycle systems of complete graphs minus a 1-factor
    (The University of Queensland, Centre for Discrete Mathematics and Computing, 2017) Jordan, Heather; Morris, Joy
    In this paper, we provide necessary and sufficient conditions for the existence of a cyclic m-cycle system of Kn −I when m and n are even and m | n.
  • Thumbnail Image
    Item
    Detecting graphical and digraphical regular representations in groups of squarefree order
    (2025) Morris, Joy; Verret, Gabriel
    A necessary condition for a Cayley digraph Cay(R,S) to be a regular representation is that there are no non-trivial group automorphisms of R that fix S setwise. A group is DRR-detecting or GRR-detecting if this condition is also sufficient for all Cayley digraphs or graphs on the group, respectively. In this paper, we determine precisely which groups of squarefree order are DRR detecting, and which are GRR-detecting.
  • Thumbnail Image
    Item
    Digraphs with small automorphism groups that are Cayley on two nonisomorphic groups
    (University of Primorska, 2020) Morgan, Luke; Morris, Joy; Verret, Gabriel
    Let Γ = 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.
  • Thumbnail Image
    Item
    Does learning about the mathematics of gambling change gambling behavior?
    (American Psychological Association, 2006-03) Williams, Robert J.; Connolly, Dennis
    The present research examined the influence of improved knowledge of odds and mathematical expectation on the gambling behavior of university students. A group of 198 Introductory Statistics students received instruction on probability theory using examples from gambling. One comparison group of 134 students received generic instruction on probability and a second group of 138 non-Statistics students received no mathematical instruction. Six months after the intervention, students receiving the intervention demonstrated superior ability to calculate gambling odds as well as resistance to gambling fallacies. Unexpectedly, this improved knowledge and skill was not associated with any decreases in actual gambling behavior. The implication of this research is that enhanced mathematical knowledge on its own may be insufficient to change gambling behavior.
  • Thumbnail Image
    Item
    Evaluating an assistant for creating bug report assignment recommenders
    (2016) Anvik, John
    Software development projects receive many change requests each day and each report must be examined to decide how the request will be handled by the project. One decision that is frequently made is to which software developer to assign the change request. Efforts have been made toward semi automating this decision,with most approaches using machine learning algorithms. However, using machine learning to create an assignment recommender is a complex process that must be tailored to each individual software development project. The Creation Assistant for Easy Assignment (CASEA) tool leverages a project member’s knowledge for creating an assignment recommender. This paper presents the results of a user study using CASEA. The user study shows that users with limited project knowledge can quickly create accurate bug report assignment recommenders.
  • Thumbnail Image
    Item
    Gambling and problem gambling in a sample of university students
    (Centre for Addiction and Mental Health, 2006-04) Williams, Robert J.; Connolly, Dennis; Wood, Robert T.; Nowatzki, Nadine R.
    University students from southern Alberta (n = 585) were administered a questionnaire to assess their gambling behaviour. Seventy-two percent reported gambling in the past 6 months, with the most common types being lotteries and instant win tickets (44%) and games of skill against other people (34%). Most students who gambled spent very little time and money doing so (median time spent = 1.5 hrs; median amount of money spent = $0). While gambling is an innocuous activity for most, a significant minority of students are heavy gamblers who experience adverse consequences from it. Seven and one-half percent of students were classified as problem or pathological gamblers, a rate significantly higher than in the general Alberta adult population. The characteristics that best differentiated problem gamblers from non-problem gamblers were more positive attitudes toward gambling, ethnicity (41% of Asian gamblers were problem gamblers), university major (kinesiology, education, management), superior ability to calculate gambling odds, and older age.
  • 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.