Mark E. Watkins
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:
- Simon M. Smith
NYC College of Technology, City University of New York
7 shared publications - Thomas W. Tucker
Department of Mathematics, Colgate University, Hamilton, USA
5 shared publications - Wilfried Imrich
Montanuniversität Leoben A-8700 Leoben Austria
3 shared publications - Jack Edward Graver
Syracuse University, United States
2 shared publications - C. Paul Bonnington
Monash University, Melbourne, VIC, Australia
1 shared publication - R. Bruce Richter
Institute for Software Technology Graz University of Technology
1 shared publication
Latest Publications
- 9 December 2019
- Published by University of Primorska Press in Ars Mathematica Contemporanea
- Vol. 17 (2) , 581-589
Lobe, edge, and arc transitivity of graphs of connectivity 1
Lobe, edge, and arc transitivity of graphs of connectivity 1
- 9 December 2019
- Published by University of Primorska Press in Ars Mathematica Contemporanea
- Vol. 17 (2) , 581-589
Lobe, edge, and arc transitivity of graphs of connectivity 1
Lobe, edge, and arc transitivity of graphs of connectivity 1
- Open Access
Growth of Face-Homogeneous Tessellations
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$.Open AccessGrowth of Face-Homogeneous Tessellations
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$. - 19 July 2014
- Published by Springer Nature in Journal of Algebraic Combinatorics
- Vol. 41 (1) , 123
Erratum to: Infinite motion and 2-distinguishability of graphs and groups
- 19 July 2014
- Published by Springer Nature in Journal of Algebraic Combinatorics
- Vol. 41 (1) , 123
Erratum to: Infinite motion and 2-distinguishability of graphs and groups
- Open Access
- 3 July 2014
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 21 (3) , P3.40
Bounding the Distinguishing Number of Infinite Graphs and Permutation Groups
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.- 3 July 2014
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 21 (3) , P3.40
Open AccessBounding the Distinguishing Number of Infinite Graphs and Permutation Groups
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
- 29 May 2014
- Published by Springer Nature in Journal of Algebraic Combinatorics
- Vol. 41 (1) , 109-122
Infinite motion and 2-distinguishability of graphs and groups
- 29 May 2014
- Published by Springer Nature in Journal of Algebraic Combinatorics
- Vol. 41 (1) , 109-122
Open AccessInfinite motion and 2-distinguishability of graphs and groups
- Open Access
Infinite Motion and 2-Distinguishability of Graphs and Groups
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 AccessInfinite Motion and 2-Distinguishability of Graphs and Groups
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
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 AccessBounding the distinguishing number of infinite graphs
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
- 7 April 2012
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 19 (2) , P27
Distinguishability of Infinite Groups and Graphs
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.- 7 April 2012
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 19 (2) , P27
Open AccessDistinguishability of Infinite Groups and Graphs
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
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 AccessDistinguishability of infinite groups and graphs
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
- 3 January 2007
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 14 (1) , R29
Distinguishability of Locally Finite Trees
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.- 3 January 2007
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 14 (1) , R29
Open AccessDistinguishability of Locally Finite Trees
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.