\documentclass[12pt]{article} \usepackage{amsfonts,amssymb,amscd,amsmath,enumerate,verbatim,calc,graphicx} \usepackage[]{color} %\usepackage[colorlinks,breaklinks,backref]{hyperref} \usepackage{e-jc} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{definition}[theorem]{Definition} \newtheorem{definitions}[theorem]{Definitions} \newtheorem{remarks}[theorem]{Remarks} \newtheorem{remark}[theorem]{Remark} \newtheorem{example}[theorem]{Example} \newtheorem{problem}[theorem]{Problem} \newtheorem{notations}[theorem]{Notations} \newtheorem{notation}[theorem]{Notation} \newtheorem{acknowledgement}{Acknowledgement} \renewcommand{\theacknowledgement}{} \newcommand{\A}{\ensuremath{\operatorname{Aut}}} \newcommand{\Sym}{\ensuremath{\operatorname{Sym}}} \newcommand{\End}{\ensuremath{\operatorname{End}}} \newcommand{\D}{\ensuremath{\operatorname{D}}} \newcommand{\V}{\ensuremath{\operatorname{V}}} \newcommand{\sk}{\ensuremath{\operatorname{S}}} \newcommand{\m}{\ensuremath{\operatorname{m}}} \newcommand{\Prob}{\ensuremath{\operatorname{Pr}}} \newcommand{\id}{\ensuremath{\text{\rm id}}} \newcommand{\dist}{\ensuremath{\operatorname{dist}}} \newcommand{\supp}{\ensuremath{\operatorname{supp}}} \newcommand{\cl}{\ensuremath{\operatorname{cl}}} \newcommand{\cg}{\overline{G}} \newcommand{\cp}{\,\square\,} \newcommand{\strong}{\boxtimes} \newcommand{\N}{{\mathbb{N}}} \newcommand{\Z}{{\mathbb{Z}}} \newcommand{\Q}{{\mathbb{Q}}} \newcommand{\R}{{\mathbb{R}}} \newcommand{\detnum}{{\rm Det}} \newcommand{\proof}{\noindent{\bf Proof\,\ }} \newcommand{\qed}{\hfill $\Box$} \newcommand{\stab}{{\rm Stab}} \newcommand{\setstab}{{\rm SetStab}} \newcommand{\ptstab}{{\rm PtStab}} \newcommand{\diam}{{\rm diam}} \newcommand{\red}{\color{red}} \newcommand{\bl}{ \color{black}} \newcommand{\rout}{\red\sout} \usepackage[normalem]{ulem} \begin{document} \title {Infinite Graphs with Finite 2-Distinguishing Cost} \author{Debra Boutin \\ Hamilton College, Clinton, NY 13323, USA \\ dboutin@hamilton.edu \and Wilfried Imrich\\ Montanuniversit\"{a}t Leoben, 8700 Leoben, Austria \\ imrich@unileoben.ac.at} %\date{April 1, 2014} \maketitle \begin{abstract} A graph $G$ is said to be 2-distinguishable if there is a labeling of the vertices with two labels such that only the trivial automorphism preserves the labels. Call the minimum size of a label class in such a labeling of $G$ the cost of 2-distinguishing $G$. Within the class of connected, locally finite, infinite graphs, we show that those with finite 2-distinguishing cost are precisely the graphs with countable automorphism group. Further we show that, for such graphs, the cost is less than three times the size of a smallest determining set (a set which only the trivial automorphism fixes pointwise). {Finally we show that graphs with} linear growth {rate $c$ have} the even smaller upper bound of {$c+1$ on their cost of 2-distinguishing}. \end{abstract} \vspace{0.5cm} \noindent {\bf Key words}: Distinguishing number, Distinguishability, Automorphism, Determining set, Determining number, Infinite graph \bigskip\noindent {\bf AMS subject classification (2000)}: 05C15, 05C25, \section{Introduction} \label{sec:intro} A labeling of the vertices of a graph $G$ with the integers $1, \ldots , d$ is called $d$-{\it distinguishing} if no nontrivial automorphism of $G$ preserves the labels. A graph is called $d$-{\it distinguishable} if it has a $d$-distinguishing labeling. This concept was introduced by Albertson and Collins in \cite{alco-96} and has spawned a wealth of results, in particular for finite graphs, but also for infinite ones.\medskip For finite graphs it was shown that many infinite families of graphs have the property that all but finitely many members are 2-distinguishable{;} see \cite{4way-2014}. Interestingly, in such cases the size of the smaller color class can be extremely small. For example the hypercube $Q_{2^k}$ of dimension $2^k$ can be 2-distinguished by coloring $k+2$ vertices black and the others white{;}\bl see \cite{bo-2013}.\medskip There are {also} large classes {of} 2-distinguishable infinite graphs. In this paper, we consider the question {of} whether one of the two color classes can be finite, and how to obtain good bounds for the size of such a class.\medskip To aid in addressing this question, we will call a label class in a 2-distinguish\-ing labeling a \emph{distinguishing class}. Following \cite{bo-2008} we call the minimum size of a distinguishing class for a 2-distinguishable graph G the {\it cost of 2-distinguishing} $G$ and denote it by $\rho(G)$.\medskip In the finite case it is natural to restrict the investigation to connected graphs. {Thus the} first natural extension to the infinite {is to}\bl connected, locally finite, infinite graphs. That is, connected graphs that are infinite, and whose vertices have finite, but possibly arbitrarily large degrees. We show that such graphs $G$ have finite $\rho(G)$ if and only if $\A(G)$ is countable. Further we provide two general bounds for $\rho(G)$ and a sharper one for graphs of linear growth.\medskip \section{Preliminaries} \label{sec:prelim} Recall that the {\it set stabilizer} of $S\subseteq V(G)$, denoted $\setstab(S)$, is the set of all $\varphi\in{\rm Aut}(G)$ for which $\varphi(x) \in S$ for all $x\in S$. In this case we say that $S$ is invariant under $\varphi$, or $\varphi$ preserves $S$, and we write $\varphi(S)=S$. The {\it point stabilizer} of $S$, denoted $\ptstab(S)$ is the set of all $\varphi\in {\rm Aut}(G)$ for which $\varphi(x)=x$ for all $x\in S$.\medskip A labeling of the vertices of a graph $G$ with the integers $1,\ldots, d$ is called a {\it $d$-distinguishing labeling} if no non-trivial automorphism of $G$ preserves the labels. A graph is called {\it $d$-distinguishable} if it has a $d$-distinguishing labeling. If a graph is 2-distinguishable, call a color class in a 2-distinguishing labeling a {\it distinguishing class} for $G$. The minimum size of a distinguishing class for a 2-distinguishable graph $G$ is called the {\it cost of $2$-distinguishing $G$} and {is}\bl denote{d} by $\rho(G)$.\medskip A significant tool used in this work is a {\it determining set} \cite{B1} (or equivalently, a {\it base} of the automorphism group action). A determining set {$S$} has the property that whenever $\varphi, \psi \in {\rm Aut}(G)$ so that $\varphi(x)=\psi(x)$ for all $x\in {S}$, then $\varphi=\psi$. Thus every automorphism of $G$ is uniquely determined by its action on the vertices of a determining set. Equivalently, a determining set is a set of vertices $S$ with $\ptstab(S)=\{\id\}$. The {\it determining number} of the graph $G$, denoted by ${\rm Det}(G)$, is the minimum size of a determining set of $G$.\medskip Note that for $F\subseteq V(G)$, an automorphisms $\varphi\in \setstab(F)$ can be thought of as a permutation in $\Sym(F)$ by restricting the action of $\varphi$ to $F$, denoted $\varphi|F$. Thus we have a natural map $\Psi:\setstab(F) \to \A(G)|F \leq \Sym(F)$. Note that this map is injective if and only if $F$ is a determining set for $G$. In such a case, we get that $\setstab(F) \cong \A(G)|F$.\medskip Albertson and Boutin showed in \cite{AB2} that a graph is $d$-distinguishable if and only if it has a determining set that is $(d-1)$-distinguishable. In particular, such a determining set is a distinguishing class for a 2-distinguishable graph $G$. Thus, a graph is $2$-distinguishable if and only if it has a determining set $S$ for which $\setstab(S) = \ptstab(S) = \{\id\}$. In such a case, the determining set and its complement provide the two necessary label classes for a 2-distinguishing labeling. Thus in particular, the cost of $2$-distinguishing a graph $G$ is bounded below by the size of a smallest determining set.\medskip The {\it motion} of an automorphism $\varphi\in \A(G)$, denoted $\m(\varphi)$, is the number of vertices moved by $\varphi$. The {\it motion} of the automorphism group, denoted {$\m(G)$}, is the minimum motion of the non-trivial elements of $\A(G)$.\medskip Throughout this paper let $\Gamma$ denote the class of infinite, connected, locally finite graphs. For such graphs Halin proved the following result, which is foundational for the work that follows. \begin{theorem}\label{thm:halin} {\rm \cite{ha-73} (Halin, 1973)} A connected, locally finite infinite graph $G$ has uncountable $\A(G)$ if and only if for every finite $F \subset V(G)$ there exists a non-trivial automorphism $\varphi$ of $G$ such that $\varphi(v) = v$ for each $v \in F$.\end{theorem} In other words, $G \in \Gamma$ has uncountable {automorphism} group if and only if it does not have a finite determining set. Therefore, a 2-distinguishable graph $G$ with uncountable {automorphism} group has infinite $\rho(G)$. We are thus interested in graphs $G$ of $\Gamma$ whose {automorphism} group is not uncountable. We first consider those that have infinite automorphism group. For them we have the following extension of Theorem \ref{thm:halin}. \begin{theorem}\label{thm:istw} {\rm \cite{4way-2014} (Imrich, Smith, Tucker, Watkins, 2014)} If $G\in \Gamma$ so that $\aleph_0 \leq |\A(G)|$ $<$ $2^{\aleph_0}$, then $\detnum(G) < \aleph_0$, $|\A(G)| = \aleph_0$, $m(G) = \aleph_0$, and $G$ is 2-distinguishable. This holds independently of the Continuum Hypothesis. \end{theorem} There is yet another consequence of Theorem \ref{thm:halin} that is folklore. It says that the vertex stabilizers of graphs $G \in \Gamma$ are finite if $\A(G)$ is countably infinite. This follows, for example, from the slightly more general Corollary 3.10 from \cite{4way-2014}. Below we state and prove a related result that invokes neither Theorem \ref{thm:halin} nor Theorem \ref{thm:istw}, but needs the following definition: The set of vertices $u\in V(G)$ for which $d(u,v)\leq n$ is called \emph{ball of radius $n$ centered at $v$,} and denoted $B_v(n)$. For later reference we also define the \emph{sphere $S_v(n)$of radius $n$ centered at $v$} as the set of vertices $u\in V(G)$ for which $d(u,v)= n$. \begin{lemma}\label{le:finite_vertex-stab} {If $G\in \Gamma$ has finite determining set, then the vertex stabilizers of $G$ are finite.} \end{lemma} \proof Suppose $B$ is a {finite} determining set for $G$ and $\ptstab(v)$ is infinite. {Since $B$ is finite, we may choose $k$ so that} $B \subseteq B_v(k)$. Hence, the orbit $C = \ptstab(v)(B)$ of $B$ {under} $\ptstab(v)$ is {a subset of} $B_v(k)$ and thus is finite. Because the infinite group $\ptstab(v)$ stabilizes the finite set $C$ {setwise}, there must be at least two different elements of $\ptstab(v)$ whose actions are identical on $C$, and thus also on $B$. {This contradicts the choice of $B$ as a determining set.} \qed \medskip \section{Countable Automorphism Group} By Theorem \ref{thm:istw} the automorphism groups of graphs $G$ in $\Gamma$ that satisfy $\aleph_0 \leq |\A(G)| < 2^{\aleph_0}$ are countable. Moreover, such graphs have infinite motion, are 2-distinguishable, and have finite determining sets. Below we show that such graphs $G$ have finite 2-distinguishing cost and give two bounds for $\rho(G)$. \begin{lemma}\label{le:finite_base_and_cost} If $G\in \Gamma$ with infinite automorphism group and $\detnum(G)=n<\aleph_0$, then $\rho(G)$ is finite and satisfies the inequality $$\rho(G) \leq n + n! -1\,.$$ \end{lemma} \proof Let $F$ be a minimum determining set for $G$. Since $F$ is a determining set, as discussed in Section \ref{sec:prelim}, $\setstab(F) \cong \A(G)|F \leq \Sym(F)$. Since $F$ is finite, so is $\Sym(F)$, and hence so is $\setstab(F)$. Let $\setstab(F) = \{\id = \alpha_0, \alpha_1, \alpha_2, \ldots, \alpha_k\}$. If $|F| = 1$, then $k = 0$. We can thus assume that $|F| > 1$.\medskip Color all elements of $F$ black and consider $\alpha_1$. By Theorem \ref{thm:istw}, $G$ has infinite motion. In other words, every nontrivial automorphism moves infinitely many vertices. Since $\alpha_1$ moves infinitely many vertices, there is a vertex $v_1$, moved by $\alpha_1$, whose distance $d(v_1, F)$ from $F$ is larger than the diameter of $F$. Color it black. Similarly there is a vertex $v_2$, moved by $\alpha_2$, with $d(v_2, F) > d(v_1, F) + \diam(F)$. Color it black as well. Similarly construct the vertices $v_3$ to $v_k$ and color them black.\medskip Suppose that $\varphi$ preserves the set of black vertices. Since each of $v_1,\ldots, v_k$ is farther from $F$ than any pair of vertices in $F$ is, $\varphi$ must preserve $F$. Thus $\varphi \in \setstab(F)$. Thus either $\varphi = id$ or $\varphi = \alpha_i$ for some $i\in[k]$. Recall that, for each $i\in [k]$, since $v_i$ is the only black vertex of distance $d(v_i,F)$ from $F$, we have that $\varphi(v_i)=v_i$. Since $v_i$ is moved by $\alpha_i$, we infer $\varphi\ne \alpha_i$. Thus $\varphi = id$ and the set of black vertices is a distinguishing class. Clearly its size is $|\setstab(F)| -1 + |F|\leq n! + n -1$. Hence, $\rho(G) < \aleph_0$.\qed\medskip Interestingly this crude bound is sharp for the 2-sided infinite path $P_{\aleph_0}$. To see this, observe that no single vertex of $P_{\aleph_0}$ can be a determining set, but that the set of end-points of any edge is a determining set. By the lemma, $\rho(P_{\aleph_0})\leq 3$. It is easy to see that $\rho(P_{\aleph_0})$ cannot be 1 or 2. Hence $\rho(P_{\aleph_0})$ = 3 and the bound is sharp.\medskip A better bound is the following, which we formulate as theorem. It uses a strong result of Cameron, Solomon and Turull \cite{casot-89}, which asserts that the largest length of a chain of subgroups of the symmetric group on $n$ elements is $\left\lceil\frac{3n}{2}\right\rceil - b(n) - 1$, where $b(n)$ denotes the number of 1s in the base-2 representation of $n$.\medskip \begin{theorem}\label{le:cameron} If $G\in \Gamma$ with infinite automorphism group and $\detnum(G)=n<\aleph_0$, then $\rho(G) \leq \left\lceil\frac{5n}{2}\right\rceil - b(n) - 1$, where $b(n)$ denotes the number of 1s in the base-2 representation of $n$. \end{theorem} \proof Let $F$ be a minimum determining set for $G$. Then $n=|F|=\detnum(G)$. Let $k, \alpha_i, v_i$ for $i\in [k]$ be as in the proof of Lemma \ref{le:finite_base_and_cost}. As shown above, coloring all elements of $F$ black breaks all automorphisms of $G$ that do not preserve $F$. The automorphisms that preserve $F$ form a (not necessarily proper) subgroup $A_0$ of $\Sym(F)$. Coloring $v_1$ black leaves a subgroup $A_1 < A_0$ of still unbroken elements of $\A(G)$. Using the notation $A_i$ for the group that preserves the set $F\cup\{v_1, \ldots, v_i\}$ we thus arrive at a chain of subgroups $$\{\id\} = A_k < A_{k-1} < \cdots < A_0$$ of length $k$. By \cite{casot-89}, $k\leq\left\lceil\frac{3n}{2}\right\rceil - b(n) - 1$. Because we colored $k + n$ vertices black the result follows.\qed\medskip Again, this bound is sharp for $P_{\aleph_0}$. From $\detnum(P_{\aleph_0})=2$ we infer $\rho(P_{\aleph_0}) \leq$ $ \lceil5\cdot|F|/2\rceil - b(|F|) - 1 = 5 - 1 -1 = 3$, which we know is the cost of 2-distinguishing $P_{\aleph_0}$. \medskip {We now combine some of the above results for our main theorem.}\smallskip \begin{theorem}\label{thm:finiterho} Let $G\in \Gamma$ with infinite automorphism group. Then $\rho(G)$ is finite if and only if $\A(G)$ is countable. \end{theorem} \proof Let $G$ be a graph in $\Gamma$ with finite $\rho(G)$. Since a distinguishing class is necessarily a determining set, we can conclude that $G$ has a finite determining set. Then, by Theorem \ref{thm:halin}, $\A(G)$ cannot be uncountable. Thus it is countable. \medskip Suppose $G \in \Gamma$ has countable automorphism group. By Theorem \ref{thm:istw}, $G$ is both 2-distinguishable and has a finite determining set. By using either Lemma \ref{le:finite_base_and_cost} or Theorem \ref{le:cameron} we conclude that $\rho(G)$ is finite.\qed \section{Linear Growth} For graphs of linear growth we can obtain an even better bound for the cost of 2-distinguishing. We begin with a few remarks about graphs of linear growth.\medskip A connected, locally finite, infinite graph $G$ is said to have \emph{linear growth} if there exists a vertex $v$ and a constant $c$, such that $|B_v(n)| \leq cn$, {for all $n\in \N$}. The definition is independent of the choice of $v$, but $c$ may have to be replaced by a different constant if $v$ is changed.\medskip Notice that $B_v(n) = \cup_{i=0}^n S_v(i)$ and that the growth is {obviously} linear if $|S_v(n)| \leq c$ for all $n$. Nonetheless, it is possible that infinitely many spheres have more than $c$ elements. Moreover, the size of the spheres need not even be bounded. We leave it to the reader to construct examples. \medskip More important for us is the fact that there must be infinitely many spheres of size at most $c$. {To see this, {suppose} only $m< \aleph_0$ of {the spheres around $v$} contain at most $c$ vertices. Consider $B_{v}(cm+1) = \cup_{i=0}^{cm+1} S_v(i)$. The $m$ spheres of size at most $c$ contain at least one vertex each, and thus in total {contain} at least $m$ vertices. The $(c-1)m+1$ spheres with more than $c$ vertices contain at least $c+1$ vertices each, and thus {contain} at least $(c+1)(cm+1-m)$ in total. Thus $|B_{v}(cm+1) | = \cup_{i=0}^{cm+1} |S_v(i)| \geq m + ((c-1)m+1)(c+1)= c(cm+1)+1$ which contradicts the assumption on the growth of $G$.} Thus there are an infinite number of spheres of size at most $c$. Because $c$ is finite, infinitely many of these spheres must have the same size.\medskip Interestingly, for graphs $G\in \Gamma$ with linear growth and infinite automorphism group, $\m(G) = \aleph_0$ if and only if $|\A(G)| = \aleph_0$. That $|\A(G)| = \aleph_0$ implies infinite motion follows from Theorem \ref{thm:istw}. The reverse implication is not hard to show. In \cite{cuimle-xx} it is attributed to \cite{4way-2014}, but only the consequence that {$G$ is 2-distinguishable} is mentioned there. As that paper contains no proof of it, we include one here for the sake of completeness. {The proof} uses the following lemma, which is similar to Lemma 2.4 in \cite{cuimle-xx}.\medskip \begin{lemma}\label{sphere} Suppose that $G$ is a connected, locally finite graph and $\A(G)$ has infinite motion. If $\alpha,\beta \in \ptstab(v)$ and $\alpha|S_v(n)=\beta|S_v(n)$ for some $n>0$, then $\alpha|B_v(n)=\beta|B_v(n)$. Furthermore, if $\alpha, \beta \in \ptstab(v)$ {have distinct actions} on $S_v(n)$, then {they have distinct actions} on all $S_v(m)$ where $m>n$. \end{lemma} \proof {Define the mapping $\gamma$ on $V(G)$ by $\gamma(u)=u$ for all $u$ with $d(v,u)\geq n$ and $\gamma(u)=\alpha\beta^{-1}(u)$ for all $u$ with $d(v,u) n$. Hence, there must be a sphere of size $c$ on which all $c! + 1$ automorphisms have distinct action. But this is impossible since there are at most $c!$ distinct actions on a set of size $c$. Thus $|\ptstab(v)| <\aleph_0$. In particular, if $G\in \Gamma$ has infinite motion and linear growth {rate $c$ from vertex $v$, then} then $|\ptstab(v)| \leq b!$ where $b \leq c$ is the minimum sphere size that occurs infinitely often.\qed \medskip {The part of the lemma which asserts that linear growth and infinite motion imply countability of the automorphisms group is based on an observation by T.~Tucker\footnote{Private communication.}.}\medskip \begin{theorem}\label{le:linear} Let $G$ be a graph with countably infinite automorphism group and linear growth. If $|B_v(n)| \leq cn$ for a fixed $v \in V(G)$ and $c\in \R$, then $\rho(G) \leq c + 1$. \end{theorem} \proof Notice first that since $G$ has a countable automorphism group, by Theorem \ref{thm:istw}, it has infinite motion. By our previous argument, there are infinitely many spheres of size at most $c$ {centered at $v$}. Denote these by {$S_i = S_v(n_i)$}, for $n_1 < n_2 < \cdots $. Since $c$ is finite, infinitely many of these spheres must have the same size. Without loss of generality we can assume that the $S_i$ already have the same size, say $d$.\medskip Note that for $j 2 \sum_{j < i }n_j\,,$$ then for $j