MWMark E. Watkins

Mark E. Watkins

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Mark E. Watkins has a total of 8 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Lobe, edge, and arc transitivity of graphs of connectivity 1

    by Jack E. Graver, Mark E. Watkins

    Lobe, edge, and arc transitivity of graphs of connectivity 1


  • Open Access

    Growth of Face-Homogeneous Tessellations

    by Stephen J. Graves, Mark E. Watkins

    A tessellation of the plane is face-homogeneous if for some integer $k\geq3$ there exists a cyclic sequence $\sigma=[p_0,p_1,\ldots,p_{k-1}]$ of integers $\geq3$ such that, for every face $f$ of the tessellation, the valences of the vertices incident with $f$ are given by the terms of $\sigma$ in either clockwise or counter-clockwise order. When a given cyclic sequence $\sigma$ is realizable in this way, it may determine a unique tessellation (up to isomorphism), in which case $\sigma$ is called monomorphic, or it may be the valence sequence of two or more non-isomorphic tessellations (polymorphic). A tessellation which whose faces are uniformly bounded in the Euclidean plane is called a Euclidean tessellation; a non-Euclidean tessellation whose faces are uniformly bounded in the hyperbolic plane is called hyperbolic. Hyperbolic tessellations are well-known to have exponential growth. We seek the face-homogeneous hyperbolic tessellation(s) of slowest growth and show that the least growth rate of monomorphic face-homogeneous tessellations is the "golden mean," $\gamma=(1+\sqrt{5})/2$, attained by the sequences $[4,6,14]$ and $[3,4,7,4]$. A polymorphic sequence may yield non-isomorphic tessellations with different growth rates. However, all such tessellations found thus far grow at rates greater than $\gamma$.

  • Erratum to: Infinite motion and 2-distinguishability of graphs and groups

    by Wilfried Imrich, Simon M. Smith, Thomas W. Tucker, Mark E. Watkins

  • Open Access

    Bounding the Distinguishing Number of Infinite Graphs and Permutation Groups

    by Simon M. Smith, Mark E. Watkins

    A group of permutations $G$ of a set $V$ is $k$-distinguishable if there exists a partition of $V$ into $k$ cells such that only the identity permutation in $G$ fixes setwise all of the cells of the partition. The least cardinal number $k$ such that $(G,V)$ is $k$-distinguishable is its distinguishing number $D(G,V)$. In particular, a graph $\Gamma$ is $k$-distinguishable if its automorphism group $\rm{Aut}(\Gamma)$ satisfies $D(\rm{Aut}(\Gamma),V\Gamma)\leq k$.Various results in the literature demonstrate that when an infinite graph fails to have some property, then often some finite subgraph is similarly deficient. In this paper we show that whenever an infinite connected graph $\Gamma$ is not $k$-distinguishable (for a given cardinal $k$), then it contains a ball of finite radius whose distinguishing number is at least $k$. Moreover, this lower bound cannot be sharpened, since for any integer $k \geq 3$ there exists an infinite, locally finite, connected graph $\Gamma$ that is not $k$-distinguishable but in which every ball of finite radius is $k$-distinguishable.In the second half of this paper we show that a large distinguishing number for an imprimitive group $G$ is traceable to a high distinguishing number either of a block of imprimitivity or of the induced action by $G$ on the corresponding system of imprimitivity. An immediate application is to automorphism groups of infinite imprimitive graphs. These results are companion to the study of the distinguishing number of infinite primitive groups and graphs in a previous paper by the authors together with T. W. Tucker.


  • Open Access

    Infinite motion and 2-distinguishability of graphs and groups

    by Wilfried Imrich, Simon M. Smith, Thomas W. Tucker, Mark E. Watkins


  • Open Access

    Infinite Motion and 2-Distinguishability of Graphs and Groups

    by Wilfried Imrich, Simon M. Smith, Thomas W. Tucker, Mark E. Watkins

    A group A acting faithfully on a set X is 2-distinguishable if there is a 2-coloring of X that is not preserved by any nonidentity element of A, equivalently, if there is a proper subset of X with trivial setwise stabilizer. The motion of an element a in A is the number of points of X that are moved by a, and the motion of the group A is the minimal motion of its nonidentity elements. For finite A, the Motion Lemma says that if the motion of A is large enough (specifically at least 2 log_2 |A|), then the action is 2-distinguishable. For many situations where X has a combinatorial or algebraic structure, the Motion Lemma implies the action of Aut(X) on X is 2-distinguishable in all but finitely many instances. We prove an infinitary version of the Motion Lemma for countably infinite permutation groups, which states that infinite motion is large enough to guarantee 2-distinguishability. From this we deduce a number of results, including the fact that every locally finite, connected graph whose automorphism group is countably infinite is 2-distinguishable. One cannot extend the Motion Lemma to uncountable permutation groups, but nonetheless we prove that 2-distinguishable permutation groups with infinite motion are dense in the class of groups with infinite motion. We conjecture an extension of the Motion Lemma which we expect holds for a restricted class of uncountable permutation groups, and we conclude with a list of open questions. The consequences of our results are drawn for orbit equivalence of infinite permutation groups.

  • Open Access

    Bounding the distinguishing number of infinite graphs

    by Simon M. Smith, Mark E. Watkins

    A group of permutations G of a set V is k-distinguishable if there exists a partition of V into k parts such that only the identity permutation in G fixes setwise all of the cells of the partition. The least cardinal number k such that (G,V) is k-distinguishable is its distinguishing number. In particular, a graph X is k-distinguishable if its automorphism group Aut(X) has distinguishing number at most k in its action on the vertices of X. Various results in the literature demonstrate that when an infinite graph fails to have some property, then often some finite subgraph is similarly deficient. In this paper we show that whenever an infinite connected graph X is not k-distinguishable (for a given cardinal k), then it contains a ball B of finite radius whose distinguishing number is at least k. Moreover, this lower bound cannot be sharpened, since for any integer k greater than 3 there exists an infinite, locally finite, connected graph X that is not k-distinguishable but in which every ball of finite radius is k-distinguishable. In the second half of this paper we show that a large distinguishing number for an imprimitive graph X is traceable to a high distinguishing number either of a block of imprimitivity or of the induced action of Aut(X) on the corresponding system of imprimitivity. The distinguishing numbers of infinite primitive graphs have been examined in detail in a previous paper by the authors together with Tom W. Tucker.

  • Open Access

    Distinguishability of Infinite Groups and Graphs

    by Simon M Smith, Thomas W Tucker, Mark E Watkins

    The distinguishing number of a group $G$ acting faithfully on a set $V$ is the least number of colors needed to color the elements of $V$ so that no non-identity element of the group preserves the coloring. The distinguishing number of a graph is the distinguishing number of its automorphism group acting on its vertex set. A connected graph $\Gamma$ is said to have connectivity 1 if there exists a vertex $\alpha \in V\Gamma$ such that $\Gamma \setminus \{\alpha\}$ is not connected. For $\alpha \in V$, an orbit of the point stabilizer $G_\alpha$ is called a suborbit of $G$.We prove that every nonnull, primitive graph with infinite diameter and countably many vertices has distinguishing number $2$. Consequently, any nonnull, infinite, primitive, locally finite graph is $2$-distinguishable; so, too, is any infinite primitive permutation group with finite suborbits. We also show that all denumerable vertex-transitive graphs of connectivity 1 and all Cartesian products of connected denumerable graphs of infinite diameter have distinguishing number $2$. All of our results follow directly from a versatile lemma which we call The Distinct Spheres Lemma.


  • Open Access

    Distinguishability of infinite groups and graphs

    by Simon M. Smith, Thomas W. Tucker, Mark E. Watkins

    The {\em distinguishing number} of a group $G$ acting faithfully on a set $V$ is the least number of colors needed to color the elements of $V$ so that no non-identity element of the group preserves the coloring. The {\em distinguishing number} of a graph is the distinguishing number of its full automorphism group acting on its vertex set. A connected graph $\Gamma$ is said to have {\em connectivity 1} if there exists a vertex $\alpha \in V\Gamma$ such that $\Gamma \setminus \{\alpha\}$ is not connected. For $\alpha \in V$, an orbit of the point stabilizer $G_\alpha$ is called a {\em suborbit} of $G$. We prove that every connected primitive graph with infinite diameter and countably many vertices has distinguishing number 2. Consequently, any infinite, connected, primitive, locally finite graph is 2-distinguishable; so, too, is any infinite primitive group with finite suborbits. We also show that all denumerable vertex-transitive graphs of connectivity 1 and all Cartesian products of connected denumerable graphs of infinite diameter have distinguishing number 2. All of our results follow directly from a versatile lemma which we call The Distinct Spheres Lemma.

  • Open Access

    Distinguishability of Locally Finite Trees

    by Mark E. Watkins, Xiangqian Zhou

    The distinguishing number $\Delta(X)$ of a graph $X$ is the least positive integer $n$ for which there exists a function $f:V(X)\to\{0,1,2,\cdots,n-1\}$ such that no nonidentity element of $\hbox{Aut}(X)$ fixes (setwise) every inverse image $f^{-1}(k)$, $k\in\{0,1,2,\cdots,n-1\}$. All infinite, locally finite trees without pendant vertices are shown to be 2-distinguishable. A proof is indicated that extends 2-distinguishability to locally countable trees without pendant vertices. It is shown that every infinite, locally finite tree $T$ with finite distinguishing number contains a finite subtree $J$ such that $\Delta(J)=\Delta(T)$. Analogous results are obtained for the distinguishing chromatic number, namely the least positive integer $n$ such that the function $f$ is also a proper vertex-coloring.