\documentclass[12pt]{article} \usepackage{e-jc} \specs{P25}{19(4)}{2012} \title{\bf Distance Powers and Distance Matrices of Integral Cayley Graphs over Abelian Groups} \author{Walter Klotz\\ {\small Institut f\"ur Mathematik}\\[-0.8ex] {\small Technische Universit\"at Clausthal, Germany}\\[-0.8ex] {\small \texttt{klotz@math.tu-clausthal.de}} \and Torsten Sander\\ \small Fakult\"at f\"ur Informatik\\[-0.8ex] \small Ostfalia Hochschule f\"ur angewandte Wissenschaften, Germany\\[-0.8ex] \small \texttt{t.sander@ostfalia.de} } \date{\dateline{May 21, 2012}{Nov 1, 2012}{Nov 8, 2012}\\ \small Mathematics Subject Classification: 05C25, 05C50} \usepackage{amsmath} \usepackage{amssymb} \usepackage{amsfonts} \usepackage{amsthm} \usepackage{centernot} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{corollary}{Corollary} \newtheorem{proposition}{Proposition} \newcommand{\Atom}{\operatorname*{Atom}} \newcommand{\ord}{\operatorname{ord}} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\Cay}{\operatorname{Cay}} \newcommand{\DM}{\operatorname{DM}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\C}{\mathbb{C}} \newcommand{\Z}{\mathbb{Z}} \newenvironment{casemarker}% {\noindent\ignorespaces}% {\par\noindent% \ignorespacesafterend} %------------------------------------------------------------------------------------------------------- \begin{document} \maketitle \begin{abstract} It is shown that distance powers of an integral Cayley graph over an abelian group $\Gamma$ are again integral Cayley graphs over $\Gamma$. Moreover, it is proved that distance matrices of integral Cayley graphs over abelian groups have integral spectrum. \end{abstract} %------------------------------------------------------------------------------------------------------- \section{Introduction} %------------------------------------------------------------------------------------------------------- Eigenvalues of an undirected graph $G$ are the eigenvalues of an arbitrary adjacency matrix of $G$. General facts about graph spectra can e.g.~be found in \cite{cvetkovic} or \cite{vandam}. Harary and Schwenk \cite{harary} defined $G$ to be {\em integral} if all of its eigenvalues are integers. For a survey of integral graphs see \cite{balinska}. In \cite{ahmadi} the number of integral graphs on $n$ vertices is estimated. Known characterizations of integral graphs are restricted to certain graph classes, see e.g.~% \cite{abdollahi}, \cite{klotz2}, or \cite{so}. Here we concentrate on integral Cayley graphs over abelian groups and their distance powers. Let $\Gamma$ be a finite, additive group, $S \subseteq \Gamma,~-S=\{-s:~s\in S\}=S$. The undirected {\em Cayley graph over $\Gamma$ with shift set (or symbol) $S$}, $\Cay(\Gamma,S)$, has vertex set $\Gamma$. Vertices $a,~b\in \Gamma$ are adjacent if and only if $a-b \in S$. For general properties of Cayley graphs we refer to Godsil and Royle \cite{godsil} or Biggs \cite{biggs}. Note that $0\in S$ generates a loop at every vertex of $\Cay(\Gamma,S)$. Many definitions of Cayley graphs exclude this case, but its inclusion saves us from sacrificing clarity of presentation later on. In our paper \cite{klotz1} we proved for an abelian group $\Gamma$ that Cay$(\Gamma,S)$ is integral if $S$ belongs to the Boolean algebra $B(\Gamma)$ generated by the subgroups of $\Gamma$. Our conjecture that the converse is true for all integral Cayley graphs over abelian groups has recently been proved by Alperin and Peterson \cite{alperin}. \begin{proposition}\label{prop1} Let $\Gamma$ be a finite abelian group, $S \subseteq \Gamma,~-S=S$. Then $G = \Cay(\Gamma,S)$ is integral if and only if $S\in B(\Gamma)$. \end{proposition} Let $G=(V,E)$ be an undirected graph with vertex set $V$ and edge set $E$, $D$ a finite set of nonnegative integers. The {\em distance power} $G^D$ of $G$ is an undirected graph with vertex set $V$. Vertices $x$ and $y$ are adjacent in $G^D$, if their distance $d(x,y)$ in $G$ belongs to $D$. We prove that if $G$ is an integral Cayley graph over the abelian group $\Gamma$, then every distance power $G^D$ is also an integral Cayley graph over $\Gamma$. Moreover, we show that in a very general sense distance matrices of integral Cayley graphs over abelian groups have integral spectrum. This extends an analogous result of Ili\'{c} \cite{ilic} for integral circulant graphs, which are the integral Cayley graphs over cyclic groups. Finally, we show that the class of gcd-graphs, another subclass of integral Cayley graphs over abelian groups (see \cite{klotz2}), is also closed under distance power operations. %------------------------------------------------------------------------------------------------------- \section{The Boolean Algebra $B(\Gamma)$} %------------------------------------------------------------------------------------------------------- Let $\Gamma$ be an arbitrary finite, additive group. We collect facts about the Boolean algebra $B(\Gamma)$ generated by the subgroups of $\Gamma$. \subsection{Atoms of $B(\Gamma)$} Let us determine the minimal elements of $B(\Gamma)$. To this end, we consider elements of $\Gamma$ to be equivalent, if they generate the same cyclic subgroup. The equivalence classes of this relation partition $\Gamma$ into nonempty disjoint subsets. We shall call these sets {\em atoms}. The atom represented by $a\in \Gamma$, $\Atom(a)$, consists of the generating elements of the cyclic group $\left$. \[ \begin{split} \Atom(a) &= \{ b\in\Gamma:~\left< a\right> = \left< b\right>\} \\ &= \{ ka:~k\in \Z,~1\leq k\leq \ord_\Gamma(a),~ \gcd(k, \ord_\Gamma(a))=1\}. \end{split} \] Here, $\Z$ stands for the set of all integers. For a positive integer $k$ and $a\in \Gamma$ we denote as usual by $ka$ the $k$-fold sum of terms $a$, $(-k)a=-(ka),~0a=0$. By $\ord_\Gamma(a)$ we mean the order of $a$ in $\Gamma$. Each set $\Atom(a)$ can be obtained by removing from $\left$ all elements of its proper subgroups. We bear in mind that every set $S\in B(\Gamma)$ can be derived from the cyclic subgroups of $\Gamma$ by means of repeated union, intersection and complement (with respect to $\Gamma$). Thus we easily arrive at the following proposition \cite{alperin}. \begin{proposition}\label{prop2} For an arbitrary finite group $\Gamma$ the following statements are true: \begin{enumerate} \item $\Atom(a) \in B(\Gamma)$ for every $a\in \Gamma$. \item For no $a\in \Gamma$ there exists a nonempty proper subset of $\Atom(a)$ that belongs to $B(\Gamma)$. \item Every nonempty set $S\in B(\Gamma)$ is the union of some sets $\Atom(a),~a\in \Gamma$. \end{enumerate} \end{proposition} %-------------------------------------------------------- \subsection{Sums of Sets in $B(\Gamma)$} In this subsection $\Gamma$ denotes a finite, additive, abelian group. We define the sum of nonempty subsets $S,~T$ of $\Gamma$: $$S+T~=~\{s+t:~s\in S,~t\in T\}.$$ We are going to show that the sum of sets in $B(\Gamma)$ is again a set in $B(\Gamma)$. \begin{lemma}\label{lem:atomsum} If $\Gamma$ is a finite abelian group and $a,~b\in\Gamma$ then $$\Atom(a)+\Atom(b)~\in~B(\Gamma).$$ \end{lemma} \begin{proof} We know that $\Gamma$ can be represented (see Cohn \cite{cohn}) as a direct sum of cyclic groups of prime power order. This can be grouped as $$\Gamma = \Gamma_1 \oplus \Gamma_2 \oplus \cdots \oplus \Gamma_r,$$ where $\Gamma_i$ is a direct sum of cyclic groups, the order of which is a power of a prime $p_i$, $|\Gamma_i|=p_i^{\alpha_i}$, $\alpha_i\geq 1$ for $i=1,\ldots,r$ and $p_i\neq p_j$ for $i\neq j$. Hence we can write each element $x\in \Gamma$ as an $r$-tuple $(x_i)$ with $x_i\in \Gamma_i$ for $i=1,\ldots,r$. The order of $x_i\in \Gamma_i$, $\ord_{\Gamma_i}(x_i)$, is a divisor of $p_i^{\alpha_i}$. Therefore, integer factors in the $i$-th coordinate of $x$ may be reduced modulo $p_i^{\alpha_i}$. The order of $x\in \Gamma$, $\ord_\Gamma(x)$, is the least common multiple of the orders of its coordinates: \begin{equation}\label{eq1} \ord_\Gamma(x)~=~\lcm(\ord_{\Gamma_1}(x_1),\ldots,\ord_{\Gamma_r}(x_r)). \end{equation} This implies that all prime divisors of $\ord_\Gamma(x)$ belong to $\{p_1,\ldots,p_r\}$. Let $a=(a_i),~b=(b_i)$ be elements of $\Gamma$. The statement of the lemma becomes trivial for $a=0$ or $b=0$. So we may assume $a\neq 0$ and $b\neq 0$. An arbitrary element $w\in \Atom(a)+\Atom(b)$ has the following form: \begin{equation}\label{eq2} \begin{split} &w~=~\lambda a+\mu b,\\ &1\leq\lambda \leq \ord_\Gamma(a),~~\gcd(\lambda,\ord_\Gamma(a))=1,\\ &1\leq\mu \leq \ord_\Gamma(b),~~\gcd(\mu,\ord_\Gamma(b))=1. \end{split} \end{equation} We have to show $\Atom(w) \subseteq \Atom(a) + \Atom(b)$. To this end, we choose the integer $\nu$ with $1\leq \nu \leq \ord_\Gamma(w)$, $\gcd(\nu,\ord_\Gamma(w))=1$, and show $\nu w \in \Atom(a)+\Atom(b)$.\\ \begin{casemarker} Case 1.~~ $(p_1p_2\cdots p_r) \mid \ord_\Gamma(w)$.\\ \end{casemarker} By $\gcd(\nu,\ord_\Gamma(w))=1$ we know that $\nu$ has no prime divisor in $\{p_1,\ldots,p_r\}$. On the other hand all prime divisors of $\ord_\Gamma(a)$ and of $\ord_\Gamma(b)$ are in $\{p_1,\ldots,p_r\}$. This implies $\gcd(\nu,\ord_\Gamma(a))=1$ and $\gcd(\nu,\ord_\Gamma(b))=1$. Setting $\lambda'=\nu \lambda$ and $\mu'=\nu \mu$ we achieve \[\begin{split} &\gcd(\lambda',\ord_\Gamma(a))=1,~\lambda' a\in \Atom(a),\\ &\gcd(\mu',\ord_\Gamma(b))=1,~\mu' b\in \Atom(b). \end{split} \] Now we have by (2): $$\nu w = \nu \lambda a +\nu \mu b = \lambda' a + \mu' b \in \Atom(a)+\Atom(b).$$ \begin{casemarker} Case 2.~~ $(p_1p_2\cdots p_r) \centernot\mid \ord_\Gamma(w)$.\\ \end{casemarker} Trivially, for $w=0\in \Atom(a)+\Atom(b)$ we have $\nu w \in \Atom(a)+\Atom(b)$. Therefore, we may assume $w\neq 0$. Without loss of generality let \begin{equation}\label{eq3} (p_1\cdots p_k)\mid \ord_\Gamma(w),~\gcd(\ord_\Gamma(w),p_{k+1}\cdots p_r)=1,~1\leq k$ is the subgroup generated by $S$ in $\Gamma$, then $G$ consists of disjoint subgraphs on the cosets of $U$, all of them isomorphic to $\Cay(U,S)$. Vertices $x,y$ in $G^{\{\infty\}}$ are adjacent if and only if they belong to different cosets of $U$, and this is true if and only if $x-y\not\in U$. Therefore, we have $$G^{\{\infty\}} = \Cay(\Gamma,S^{(\infty)}) \text{ with } S^{(\infty)}=\overline{U}=\Gamma \backslash U\in B(\Gamma).$$ Assume now that $d\geq 1$ is a finite distance attained between vertices $x,y$ in $G$. The sequence of vertices in a shortest path $P$ between $x$ and $y$ in $G=\Cay(\Gamma,S)$ has the form $$x,x+s_1,x+s_1+s_2,\ldots,x+s_1+\ldots+s_d = y,~s_i\in S \text{ for }1\leq i\leq d.$$ This implies $y-x = s_1+\ldots +s_d \in dS$, where $dS$ denotes the $d$-fold sum of the set $S$. To guarantee that there is no shorter path from $x$ to $y$ than $P$ we remove from $dS$ all multiples $kS$ for $0\leq k