Dave Witte Morris' papers in graph theory

  1. On Hamiltonian circuits in Cayley diagrams. Discrete Math. 38 (1982) 99-108.
    2. This paper proves the existence of hamiltonian circuits in Cayley digraphs on various groups. Most of the results are now obsolete, due to further work of the author and others.
  2. with Douglas Dunham and John Lindgren: Creating repeating hyperbolic patterns. Computer Graphics 15 (1981) 215-223.
    3. This paper describes an algorithm to produce repeating patterns in the style of the artist M. C. Escher.
  3. with Gail Letzter and Joseph A. Gallian: On hamiltonian circuits in cartesian products of Cayley digraphs. Discrete Math. 43 (1983) 297-307.
    4. This paper exhibits a hamiltonian circuit in the natural Cayley digraph on the direct product of a cyclic group and a dihedral, semidihedral, or dicyclic group.
  4. with Stephen J. Curran: Hamilton paths in cartesian products of directed cycles. Ann. Discrete Math. 27 (1985) 35-74.
    5. This paper finds all the hamiltonian paths in the cartesian product of two directed cycles, and uses these paths to prove there is a hamiltonian circuit in the cartesian product of any three or more directed cycles.
  5. with Laurence E. Penn: When the cartesian product of two directed cycles is hypo-hamiltonian. J. Graph Theory 7 (1983) 441-443.
    6. This paper uses Curran's ideas [4] to determine the lengths of all simple circuits in the cartesian product of any two directed cycles.
  6. with Kevin Keating: On Hamilton cycles in Cayley graphs with cyclic commutator subgroup. Ann. Discrete Math. 27 (1985) 89-102.
    7. This paper finds a hamiltonian cycle in every (undirected) Cayley graph on any group whose commutator subgroup is cyclic of prime-power order.
  7. with Joseph A. Gallian: A survey: hamiltonian cycles in Cayley graphs. Discrete Math. 51 (1984) 293-304.
    It has been conjectured there is a hamiltonian cycle in every (undirected) Cayley graph. This paper is a research-level survey of results, techniques, and open problems in the field, with a comprehensive bibliography. It is now somewhat out of date.
  8. with Joseph A. Gallian: Hamiltonian checkerboards. Math. Mag. 57 (1984) 291-294.
    This paper is an undergraduate-level survey of my work with Curran, and an introduction to the more general study of hamiltonian circuits in Cayley digraphs.
  9. Cayley digraphs of prime-power order are hamiltonian. J. Comb. Th. B 40 (1986) 107-112.
    10. This paper proves that Cayley digraphs of prime-power order have a hamiltonian circuit. Previously, it had not been shown that these Cayley digraphs have a hamiltonian path, not even an undirected one.
  10. with Joseph A. Gallian: When the cartesian product of two directed cycles is hyperhamiltonian. J. Graph Th. 11 (1987) 21-24.
    11. This paper uses Curran's ideas [4] to determine when there is a closed, spanning walk with just one repeated vertex.
  11. with Brian Alspach and Stephen C. Locke:The Hamilton spaces of Cayley graphs on abelian groups. Discrete Math. 82 (1990) 113-126.
    12. For any Cayley graph on any finite abelian group, this paper determines precisely which elements of the cycle space can be written as sums of hamiltonian cycles.
  12. with Stephen C. Locke: Flows in circulant graphs of odd order are sums of Hamilton cycles. Discrete Math. 78 (1989) 105-114.
    13. For any Cayley graph on any finite abelian group of odd order, this paper determines precisely which flows can be written as sums of hamiltonian cycles. This is a sequel to my work with Alspach and Locke [9].
  13. with Michael Reid and Douglas S. Jungreis: Distances forbidden by some two-coloring of Q2. Discrete Math. 82 (1990) 53-56.
    14. For any possible distance d > 0, this note determines whether there is a 2-coloring of the rational points in the plane such that the distance between two points of the same color is never 1 or d. This completes work of P. D. Johnson, Jr..
  14. Hamilton-decomposable graphs and digraphs of infinite valence. Discrete Math. 84 (1990) 87-100.
    15. This paper shows that any regular graph of infinite valence that has a two-way-infinite hamiltonian path either has infinite connectivity or can be constructed in a simple way by combining two graphs with infinite connectivity. The paper also considers directed graphs.
  15. with Douglas Dunham and Douglas S. Jungreis: Infinite hamiltonian paths in Cayley digraphs of hyperbolic symmetry groups. Discrete Math. 143 (1995) 1-30.
    16. The hyperbolic symmetry groups [p, q], [p, q]+, and [p+,q] have certain natural generating sets; this paper determines whether or not the corresponding Cayley digraphs have one-way-infinite or two-way-infinite hamiltonian paths. In addition, the analogous undirected Cayley graphs are shown to have infinite hamiltonian paths of both types.
  16. with Tomaz Pisanski and Thomas W. Tucker: The non-orientable genus of some metacyclic groups. Combinatorica 12 (1992) 77-87.
    17. This paper shows that certain Cayley graphs of finite, metacyclic groups can be embedded nicely on non-orientable surfaces. This yields the first known construction of Cayley graphs for which 2g - g' is arbitrarily large, where g and g' are the orientable genus and the non-orientable genus of the Cayley graph.
  17. with Margaret H. Forbush, Elizabeth Hanson, Susan Kim, Andrew Mauer, Rhian Merris, Seth Oldham, Jennifer O. Sargent, and Kate Sharkey: Hamiltonian paths in projective checkerboards. Ars Combinatoria 56 (2000) 147-160.
    18. Construct a projective plane from an n by n checkerboard, by gluing together opposite edges of the board (with a twist). This paper gives an explicit description of the routes that visit all the squares of the checkerboard, without repetition.
  18. with Edward Dobson, Heather Gavlas, and Joy Morris: Automorphism groups with cyclic commutator subgroup and Hamilton cycles, Discrete Math.189 (1998) 69-78. (arXiv:math.CO/9702226)
    19. D. Witte and K. Keating [6] showed that there is a Hamilton cycle in every connected Cayley graph on each group G whose commutator subgroup is cyclic of prime-power order. This paper considers connected, vertex-transitive graphs X of order at least 3 where the automorphism group of X contains a transitive subgroup G whose commutator subgroup is cyclic of prime-power order. We show that of these graphs, only the Petersen graph is not hamiltonian.
  19. with Stephen C. Locke: On non-hamiltonian circulant digraphs of outdegree three. J. Graph Theory 30 (1999) 319-331. (arXiv:math.CO/9702227)
      20.  
      We construct infinitely many connected, circulant digraphs of outdegree three that have no hamiltonian circuit. All of our examples have an even number of vertices, and our examples are of two types: either every vertex in the digraph is adjacent to two diametrically opposite vertices, or every vertex is adjacent to the vertex diametrically opposite to itself.
       
  20. with Edward Dobson: Transitive permutation groups of prime-squared degree. J. Algebraic Combinatorics 16 (2002) 43-69. (arXiv:math.GR/0012192)
      21.  
      We explicitly determine all of the transitive groups of degree p-squared, p a prime, whose Sylow p-subgroup is not the wreath product of two cyclic groups of order p. Furthermore, we provide a general description of the transitive groups of degree p-squared whose Sylow p-subgroup is such a wreath product, and explicitly determine most of them. As applications, we solve the Cayley Isomorphism problem for Cayley objects of an abelian group of order p-squared, explicitly determine the full automorphism group of Cayley graphs of abelian groups of order p-squared, and find all nonnormal Cayley graphs of order p-squared.

      Correction:  Theorem 12 of this paper is incorrect. For an accurate description of the codes invariant under a subgroup of PΓL(d,q), see Proposition 1.4, Theorem 1.5, and Section 3 of [J.D.Dixon and A.E.Zalesski, Finite imprimitive linear groups of prime degree, J. Algebra 276 (2004), no. 1, 340-370]. Corollary 3.8 of that paper tells us every PSL(d,q)-invariant code is also PΓL(d,q)-invariant, which is not what our Theorem 12 would indicate. We thank Primoz Potocnik for both pointing out our error and explaining where to find the correct result in the literature.

  21. with David Austin and Heather Gavlas: Hamiltonian paths in Cartesian powers of directed cycles. Graphs and Combinatorics 19 (2003) 459-466. (arXiv:math.CO/0110073)
      22.  
      The vertex set of the kth cartesian power of a directed cycle of length m can be naturally identified with the abelian group (Zm)k. For any two elements v = (v1,...,vk) and w = (w1,...,wk) of (Zm)k, it is easy to see that if there is a hamiltonian path from v to w, then v1 + ... + vk = w1 + ... + wk + 1 (mod m).  We prove the converse, unless k = 2 and m is odd.
       
  22. with Joy Morris and David Petrie Moulton: Flows that are sums of hamiltonian cycles in abelian Cayley graphs. Discrete Mathematics 299 (2005) 208–268. (arXiv:math.CO/0309050)
      23.  
      If X is any connected Cayley graph on any finite abelian group, we determine precisely which flows on X can be written as a sum of hamiltonian cycles. (This answers a question of Brian Alspach.) In particular, if the degree of X is at least 5, and X has an even number of vertices, then the flows that can be so written are precisely the even flows, that is, the flows f, such that the sum of the edge-flows of f is divisible by 2. On the other hand, there are examples of degree 4 in which not all even flows can be written as a sum of hamiltonian cycles. Analogous results were already known, from work of Alspach, Locke, and Witte, for the case where X is cubic, or has an odd number of vertices.

  23. with Joy Morris and Kerri Webb: Hamiltonian cycles in (2,3,c)-circulant digraphs, Discrete Mathematics 309 (2009) 5484–5490. (arXiv:math.CO/0610010)
      24.  
      Let D be the circulant digraph with n vertices and connection set {2, 3, c}. (Assume D is loopless and has outdegree 3.) Work of S.C.Locke and D.Witte implies that if n is a multiple of 6, c is either (n/2) + 2 or (n/2) + 3, and c is even, then D does not have a hamiltonian cycle. For all other cases, we construct a hamiltonian cycle in D.