Electronic Journal of Graph Theory and Applications

Seyed Morteza Mirafzal, Ali Zafari

Department of Mathematics Lorestan University, Khoramabad, Iran

morteza_mirafzal@yahoo.com, mirafzal.m@lu.ac.ir, zafari.math.pu@gmail.com

Let \(\Gamma = Cay(\mathbb{Z}_n, S_k)\) be the Cayley graph on the cyclic additive group \(\mathbb{Z}_n\) \((n \geq 4)\), where \(S_1 = \{1, n-1\}, \ldots, S_k = S_{k-1} \cup \{k, n-k\}\) are the inverse-closed subsets of \(\mathbb{Z}_n - \{0\}\) for any \(k \in \mathbb{N}\), \(1 \leq k \leq \left[\frac{n}{2}\right] - 1\). In this paper, we will show that \(\chi(\Gamma) = \omega(\Gamma) = k+1\) if and only if k+1|n. Also, we will show that if n is an even integer and \(k = \frac{n}{2} - 1\) then \(Aut(\Gamma) \cong \mathbb{Z}_2 wr_I Sym(k+1)\) where \(I = \{1, \ldots, k+1\}\) and in this case, we show that \(\Gamma\) is an integral graph.

Keywords: Cayley graph, distance-transitive, wreath product Mathematics Subject Classification: 05C15, 05C50 DOI:10.5614/ejgta.2017.5.1.7

1. Introduction

In this paper, a graph \(\Gamma=(V,E)\) always means a simple connected graph with n vertices (without loops, multiple edges and isolated vertices), where \(V=V(\Gamma)\) is the vertex set and \(E=E(\Gamma)\) is the edge set. The size of the largest clique in the graph \(\Gamma\) is denoted by \(\omega(\Gamma)\) and the size of the largest independent sets of vertices by \(\alpha(\Gamma)\). A graph \(\Gamma\) is called a vertex-transitive graph if for any \(x,y\in V\) there is some \(\pi\) in \(Aut(\Gamma)\), the automorphism group of \(\Gamma\), such that \(\pi(x)=y\). Let \(\Gamma\) be a graph, the complement \(\overline{\Gamma}\) of \(\Gamma\) is the graph whose vertex set is \(V(\Gamma)\) and whose edges are the pairs of nonadjacent vertices of \(\Gamma\). It is well known that for any graph \(\Gamma\), \(Aut(\Gamma)=Aut(\overline{\Gamma})\)

Received: 8 September 2016, Revised: 15 January 2017, Accepted: 7 February 2017.

[8]. If \(\Gamma\) is a connected graph and \(\partial(u,v)\) denotes the distance in \(\Gamma\) between the vertices u and v, then for any automorphism \(\pi\) in \(Aut(\Gamma)\) we have \(\partial(u,v) = \partial(\pi(u),\pi(v))\).

Let k be a positive integer, a k-colouring of a graph \(\Gamma\) is a mapping \(f\colon V(\Gamma)\longrightarrow \{1,\ldots,k\}\) such that \(f(x)\neq f(y)\) for any two adjacent vertices x and y in \(\Gamma\), and if such a mapping exists we say that \(\Gamma\) is k-colorable. The chromatic number \(\chi(\Gamma)\) of \(\Gamma\) is the minimum number k such that \(\Gamma\) is k-colorable. Let \(\Gamma\) be a graph and \(\mathcal{I}(\Gamma)\) denote the set of all independent sets of the graph \(\Gamma\). A fractional colouring of a graph \(\Gamma\) is a weight function \(\mu\colon \mathcal{I}(\Gamma)\longrightarrow [0,1]\) such that for any vertex x of \(\Gamma\), \(\sum_{x\in I\in\mathcal{I}(\Gamma)}\mu(I)\geq 1\), and if such a weight function exists we say that \(\Gamma\) is fractional colouring. The fractional chromatic number of a graph \(\Gamma\) is denoted by \(\chi_f(\Gamma)\) and defined in [9, Page 134]. Also a fractional clique of a graph \(\Gamma\) is denoted by \(\psi_f(\Gamma)\) and defined in [9, Page 134].

Let \(\Upsilon = \{\gamma_1, \dots, \gamma_{k+1}\}\) be a set and K be a group then we write \(Fun(\Upsilon, K)\) to denote the set of all functions from \(\Upsilon\) into K, we can turn \(Fun(\Upsilon, K)\) into a group by defining a product:

\[(fg)(\gamma) = f(\gamma)g(\gamma)\] for all \(f, g \in Fun(\Upsilon, K)\) and \(\gamma \in \Upsilon\),

where the product on the right is in K. Since \(\Upsilon\) is finite, the group \(Fun(\Upsilon, K)\) is isomorphic to \(K^{k+1}\) (a direct product of k+1 copies of K) via the isomorphism \(f \to (f(\gamma_1), \ldots, f(\gamma_{k+1}))\). Let H and K be groups and suppose H acts on the nonempty set \(\Upsilon\). Then the wreath product of K by H with respect to this action is defined to be the semidirect product \(Fun(\Upsilon, K) \rtimes H\) where H acts on the group \(Fun(\Upsilon, K)\) via

\[f^x(\gamma) = f(\gamma^{x^{-1}})\] for all \(f \in Fun(\Upsilon, K), \gamma \in \Upsilon\) and \(x \in H\).

We denote this group by \(Kwr_{\Upsilon}H\). Consider the wreath product \(G=Kwr_{\Upsilon}H\). If K acts on a set \(\Delta\) then we can define an action of G on \(\Delta \times \Upsilon\) by

\[(\delta, \gamma)^{(f,h)} = (\delta^{f(\gamma)}, \gamma^h)\] for all \((\delta, \gamma) \in \Delta \times \Upsilon\),

where \((f,h) \in Fun(\Upsilon,K) \rtimes H = Kwr_{\Upsilon}H\) [6].

Eigenvalues of an undirected graph \(\Gamma\) are the eigenvalues of an arbitrary adjacency matrix of \(\Gamma\). Harary and Schwenk [10] defined \(\Gamma\) to be integral, if all of its eigenvalues are integers. For a survey of integral graphs see [3]. In [2] the number of integral graphs on n vertices is estimated. Known characterizations of integral graphs are restricted to certain graph classes, see [1].

Let G be a finite group and S a subset of G that is closed under taking inverses and does not contain the identity. A Cayley graph \(\Gamma = Cay(G, S)\) is a graph whose vertex-set and edge-set are defined as follows:

\[V(\Gamma) = G; \quad E(\Gamma) = \{ \{x, y\} \mid x^{-1}y \in S \}.\]

It is well known that every Cayley graph is vertex-transitive.

For any graph \(\Gamma\), \(\omega(\Gamma) \leq \chi(\Gamma)\) [8]. Also it is well known that for bipartite graphs \(\omega(\Gamma) = \chi(\Gamma) = 2\). Let \(\Gamma\) be the \(Cay(\mathbb{Z}_n, S_k)\) where \(\mathbb{Z}_n\) \((n \geq 4)\), is the cyclic additive group with identity \(\{0\}\), and for any \(k \in \mathbb{N}\), \(1 \leq k \leq \left[\frac{n}{2}\right] - 1\), \(S_1 = \{1, n-1\}, \ldots, S_k = S_{k-1} \cup \{k, n-k\}\) are inverse-closed subsets of \(\mathbb{Z}_n - \{0\}\). In this paper we will show that \(\chi(\Gamma) = \omega(\Gamma) = k+1\) if and only if k+1|n, also we show that if n is an even integer and \(k = \frac{n}{2} - 1\) then \(Aut(\Gamma) \cong \mathbb{Z}_2wr_ISym(k+1)\), where \(I = \{1, \ldots, k+1\}\).

2. Definitions and Preliminaries

Proposition 2.1. [11] For any graph Γ we have

\[\omega(\Gamma) \le \omega_f(\Gamma) \le \chi_f(\Gamma) \le \chi(\Gamma).\]

Proposition 2.2. [8] If Γ is vertex transitive graph, then we have

\[\omega_f(\Gamma) = \frac{|V(\Gamma)|}{\alpha(\Gamma)}\]

Definition 1. [4] Let Γ be a graph with automorphism group Aut(Γ). We say that Γ is symmetric if, for all vertices u, v, x, y of Γ such that u and v are adjacent, also, x and y are adjacent, there is an automorphism π such that π(u) = x and π(v) = y. We say that Γ is distance-transitive if, for all vertices u, v, x, y of Γ such that ∂(u, v) = ∂(x, y), there is an automorphism π such that π(u) = x and π(v) = y.

Remark 2.1. [4] Let Γ be a graph. It is clear that we have a hierarchy of conditions: distance-transitive ⇒ symmetric ⇒ vertex-transitive

Definition 2. [4], [5] For any vertex v of a connected graph Γ we define

\[\Gamma_r(v) = \{ u \in V(\Gamma) \mid \partial(u, v) = r \},\\]

where r is a non-negative integer not exceeding d, the diameter of Γ. It is clear that Γ0(v) = {v}, and V (Γ) is partitioned into the disjoint subsets Γ0(v), . . . , Γd(v), for each v in V (Γ). The graph Γ is called distance-regular with diameter d and intersection array {b0, . . . , bd−1; c1, . . . , cd}, if it is regular of valency k and for any two vertices u and v in Γ at distance r we have |Γr+1(v)∩Γ1(u)| = br, and |Γr−1(v) ∩ Γ1(u)| = cr, (0 ≤ r ≤ d). The numbers cr, b^r and ar, where

\[a_r = k - b_r - c_r \quad (0 \le r \le d),\]

is the number of neighbours of u in Γr(v) for ∂(u, v) = r, are called the intersection numbers of Γ. Clearly b⁰ = k, b^d = c⁰ = 0 and c¹ = 1.

Remark 2.2. [4] It is clear that if Γ is distance-transitive graph then Γ is distance-regular.

Lemma 2.1. [4] A connected graph Γ with diameter d and automorphism group G = Aut(Γ) is distance-transitive if and only if it is vertex-transitive and the vertex-stabilizer G^v is transitive on the set Γr(v), for each r ∈ {0, 1, . . . , d}, and v ∈ V (Γ).

Theorem 2.1. [5] Let Γ be a distance-regular graph which the valency of each vertex as k, with diameter d, adjacency matrix A and intersection array,

\[\{b_0, b_1, \ldots, b_{d-1}; c_1, c_2, \ldots, c_d\}.\]

Then the tridiagonal (d + 1) × (d + 1) matrix

\[\jmath(\Gamma) = \begin{bmatrix} a_0 & b_0 & 0 & 0 & \dots & & & \\ c_1 & a_1 & b_1 & 0 & \dots & & & \\ 0 & c_2 & a_2 & b_2 & & & & & \\ & & \cdots & & & & & \\ & & & c_{d-2} & a_{d-2} & b_{d-2} & 0 \\ & & \dots & 0 & c_{d-1} & a_{d-1} & b_{d-1} \\ & & \dots & 0 & 0 & c_d & a_d \end{bmatrix},\]

determines all the eigenvalues of \(\Gamma\).

Theorem 2.2. [7] Let \(\Gamma\) be a graph such that contains k+1 components \(\Gamma_1, \ldots, \Gamma_{k+1}\). If for any \(i \in I = \{1, \ldots, k+1\}\), \(\Gamma_i \cong \Gamma_1\) then \(Aut(\Gamma) \cong Aut(\Gamma_1)wr_ISym(k+1)\).

3. Main Results

Proposition 3.1. Let \(\Gamma = Cay(\mathbb{Z}_n, S_k)\) be the Cayley graph on the cyclic group \(\mathbb{Z}_n\) \((n \ge 4)\), where \(S_1 = \{1, n-1\}, \ldots, S_k = S_{k-1} \cup \{k, n-k\}\) are the inverse-closed subsets of \(\mathbb{Z}_n - \{0\}\) for any \(k \in \mathbb{N}\), \(1 \le k \le \left[\frac{n}{2}\right] - 1\). Then \(\chi(\Gamma) = \omega(\Gamma) = k+1\) if and only if k+1|n.

Proof. By definition of \(S_i\), \(1 \le i \le k\) clearly \(|S_i| = 2i\), hence \(|S_k| = 2k\). Let \(\Gamma = Cay(\mathbb{Z}_n, S_k)\) be the Cayley graph on the cyclic group \(\mathbb{Z}_n\) and \(S_k\) be the set of inverse-closed subset of \(\mathbb{Z}_n - \{0\}\) which is defined as before. By definition of \(\Gamma\) clearly \(\omega(\Gamma) = k + 1\). So, if \(\chi(\Gamma) = \omega(\Gamma) = k + 1\) then by Proposition 2.1, \(\chi_f(\Gamma) = \omega_f(\Gamma) = k + 1\). Also we know that \(\Gamma\) is a vertex transitive graph, so by Proposition 2.2, \(k + 1 = \omega_f(\Gamma) = \frac{|V(\Gamma)|}{\alpha(\Gamma)}\) therefore k + 1|n. Conversely, if k + 1|n then \(\chi(\Gamma) = k + 1\), because \(\Gamma\) is a vertex transitive graph and the size of every clique in the graph \(\Gamma\) is k + 1, therefore \(\chi(\Gamma) = \omega(\Gamma) = k + 1\).

Example 1. Suppose \(\Gamma_1 = Cay(\mathbb{Z}_{12}, S_2)\) and \(\Gamma_2 = Cay(\mathbb{Z}_{12}, S_3)\) are two Cayley graphs, then \(\chi(\Gamma_1) = \omega(\Gamma_1) = 3\) and \(\chi(\Gamma_2) = \omega(\Gamma_2) = 4\).

Figure 1: \(\chi(\Gamma_1) = \omega(\Gamma_1) = 3\) Figure 2: \(\chi(\Gamma_2) = \omega(\Gamma_2) = 4\)

Proposition 3.2. Let \(\Gamma = Cay(\mathbb{Z}_n, S_k)\) be the Cayley graph on the cyclic group \(\mathbb{Z}_n\) \((n \ge 4)\), where \(S_1 = \{1, n-1\}, \ldots, S_k = S_{k-1} \cup \{k, n-k\}\) are the inverse-closed subsets of \(\mathbb{Z}_n - \{0\}\) for any \(k \in \mathbb{N}\), \(1 \le k \le \left[\frac{n}{2}\right] - 1\). If n is an even integer and \(k = \frac{n}{2} - 1\) then \(Aut(\Gamma) \cong \mathbb{Z}_2wr_ISym(k+1)\), where \(I = \{1, \ldots, k+1\}\).

Proof. Let \(V(\Gamma)=\{1,\ldots,n\}\) be the vertex set of \(\Gamma\). By assumptions and Proposition 2.2, the size of the largest independent set of vertices in the \(\Gamma\) is 2, because \(\Gamma\) is a vertex transitive graph and the size of every clique in the graph \(\Gamma\) is k+1. Thus, the size of the every independent set of vertices in the \(\Gamma\) is 2. Therefore for any \(x\in V(\Gamma)\), there is exactly one \(y\in V(\Gamma)\) such that \(x^{-1}y=k+1\). Hence, if \(x^{-1}y=k+1\) then two vertices x and y adjacent in the complement \(\overline{\Gamma}\) of \(\Gamma\), so \(\overline{\Gamma}\) contains k+1 components \(\Gamma_1,\ldots,\Gamma_{k+1}\) such that for any \(i\in I=\{1,\ldots,k+1\}\), \(\Gamma_i\cong \Gamma_1\cong K_2\), where \(K_2\) is the complete graph of 2 vertices. Therefore \(\overline{\Gamma}\cong (k+1)K_2\), hence by Theorem 2.2, \(Aut(\overline{\Gamma})\cong Aut(K_2)wr_ISym(k+1)=\mathbb{Z}_2wr_ISym(k+1)\), so \(Aut(\Gamma)\cong \mathbb{Z}_2wr_ISym(k+1)\). \(\square\)

Example 2. Let \(\Gamma = Cay(\mathbb{Z}_{12}, S_5)\) be the Cayley graph on the cyclic group \(\mathbb{Z}_{12}\), then \(\chi(\Gamma) = \omega(\Gamma) = 6\), and \(Aut(\Gamma) = \mathbb{Z}_2wr_ISym(6)\), where \(I = \{1, \ldots, 6\}\).

Figure 3: \(\chi(\Gamma) = \omega(\Gamma) = 6\)

Proposition 3.3. Let \(\Gamma = Cay(\mathbb{Z}_n, S_k)\) be the Cayley graph on the cyclic group \(\mathbb{Z}_n\) \((n \ge 4)\), where \(S_1 = \{1, n-1\}, \ldots, S_k = S_{k-1} \cup \{k, n-k\}\) are the inverse-closed subsets of \(\mathbb{Z}_n - \{0\}\) for any \(k \in \mathbb{N}\), \(1 \le k \le \left[\frac{n}{2}\right] - 1\). If n is an even integer and \(k = \frac{n}{2} - 1\) then \(\Gamma\) is a distance-transitive graph.

Proof. By Lemma 2.1, it is sufficient to show that vertex-stabilizer \(G_v\) is transitive on the set \(\Gamma_r(v)\) for every \(r \in \{0,1,2\}\) and \(v \in V(\Gamma)\), because of \(\Gamma\) is a vertex-transitive graph. We know \(V(\Gamma) = \{1,2,\ldots,\frac{n}{2}-1,\frac{n}{2},\frac{n}{2}+1,\ldots,n\}\) is the vertex set of \(\Gamma\). Let \(G=Aut(\Gamma)\). Consider the vertex v=1 in the \(V(\Gamma)\), then \(\Gamma_0(v)=\{1\}, \Gamma_1(v)=\{2,\ldots,\frac{n}{2}-1,\frac{n}{2},\frac{n}{2}+2,\ldots,n\}\) and \(\Gamma_2(v)=\{\frac{n}{2}+1\}\). Let \(\rho=(2,3,\ldots,\frac{n}{2},\frac{n}{2}+2,\ldots,n)\) be the cyclic permutation of the vertex set of \(\Gamma\). It is an easy task to show that \(\rho\) is an automorphism of \(\Gamma\). We can show that \(H=\langle (2,3,\ldots,\frac{n}{2},\frac{n}{2}+2,\ldots,n)\rangle\) acts transitively on the set \(\Gamma_r(v)\) for each \(r \in \{0,1,2\}\), because H is a cyclic group. Note that if \(1 \neq v \in V(\Gamma)\) then, we can show that vertex-stabilizer \(G_v\) is transitive on the set \(\Gamma_r(v)\) for each \(r \in \{0,1,2\}\), because \(\Gamma\) is a vertex-transitive graph. \(\square\)

Proposition 3.4. Let \(\Gamma = Cay(\mathbb{Z}_n, S_k)\) be the Cayley graph on the cyclic group \(\mathbb{Z}_n\) \((n \ge 4)\), where \(S_1 = \{1, n-1\}, \ldots, S_k = S_{k-1} \cup \{k, n-k\}\) are the inverse-closed subsets of \(\mathbb{Z}_n - \{0\}\) for any \(k \in \mathbb{N}\), \(1 \le k \le \left[\frac{n}{2}\right] - 1\). If n is an even integer and \(k = \frac{n}{2} - 1\) then \(\Gamma\) is an integral graph.

Proof. By Remark 2.2, it is clear that \(\Gamma\) is distance-regular, because \(\Gamma\) is a distance-transitive graph. Let \(V(\Gamma)=\{1,2,\ldots,n\}\) be the vertex set of \(\Gamma\). Consider the vertex v=1 in the \(V(\Gamma)\), then \(\Gamma_0(v)=\{1\}, \, \Gamma_1(v)=\{2,\ldots,\frac{n}{2}-1,\frac{n}{2},\frac{n}{2}+2,\ldots,n\}\) and \(\Gamma_2(v)=\{\frac{n}{2}+1\}\). Let be u in the \(V(\Gamma)\) such that \(\partial(u,v)=0\) then u=v=1 and \(|\Gamma_1(v)\cap\Gamma_1(u)|=2k\), hence \(b_0=2k\) and by Definition 2, \(a_0=2k-b_0=0\). Also, if u in the \(V(\Gamma)\) and \(\partial(u,v)=1\) then two vertices u,v are adjacent in \(\Gamma\), so \(|\Gamma_0(v)\cap\Gamma_1(u)|=1\) and \(|\Gamma_2(v)\cap\Gamma_1(u)|=1\), hence \(c_1=1,\,b_1=1\) and \(a_1=2k-b_1-c_1=2k-2\). Finally, if u in the \(V(\Gamma)\) and \(\partial(u,v)=2\) then two vertices u,v are not adjacent in \(\Gamma\), so \(|\Gamma_1(v)\cap\Gamma_1(u)|=2k\), hence \(c_2=2k\) and \(a_2=2k-c_2=0\). So the intersection array of \(\Gamma\) is \(\{2k,1;1,2k\}\). Therefore by Theorem 2.1, the tridiagonal \((3)\times(3)\) matrix,

\[\begin{bmatrix} a_0 & b_0 & 0 \\ c_1 & a_1 & b_1 \\ 0 & c_2 & a_2 \end{bmatrix} = \begin{bmatrix} 0 & 2k & 0 \\ 1 & 2k - 2 & 1 \\ 0 & 2k & 0 \end{bmatrix},\]

determines all the eigenvalues of \(\Gamma\). It is clear that all the eigenvalues of \(\Gamma\) are 2k, 0, -2 and their multiplicities are 1, k+1, k, respectively. So \(\Gamma\) is an integral graph.

References

• [1] A. Abdollahi and E. Vatandoost, Which Cayley graphs are integral?, Electron. J. Comb. 16 (1) (2009), r122, 1–17.
• [2] O. Ahmadi, N. Alon, L.F. Blake and I.E. Shparlinski, Graphs with integral spectrum, Linear Alg. Appl. 430 (2009), 547–552.
• [3] K. Balinska, D. Cvetković, Z. Rodosavljević, S. Simić and D.Ste-vanović, A survey on integral graphs, Univ. Beograd, Publ. Elektrotehn. Fak. Ser. Mat. 13 (2002), 42–65.
• [4] N.L. Biggs, Algebraic Graph Theory, New York, NY, Cambridge University Press, Cambridge, 1993.
• [5] A.E. Brower, A.M. Cohen and A. Neumaier, Distance Regular Graphs, Springer, Berlin, 1989.
• [6] J. D. Dixon and B. Mortimer, Permutation Groups, Math. Proc, Cambridge Phil. Soc, 1996.
• [7] R. Frucht, On the groups of repeated graphs, Bulletin of the American Mathematical Society 55 (1949), 418–420.
• [8] C. Godsil and G. Royle, Algebraic graph theory, Springer, New York, 2001.
• [9] Geňa Hahn and Claude Tardif, Graph homomorphisms: structure and symmetry, Mathematical and Physical Sciences 497 (1997), 107–166.

• [10] F. Harary and A. Schwenk, Which graphs have integral spectra?, Lect. Notes Math., Springer Verlag 406 (1974), 45–50.
• [11] E.R. Scheinerman and D.H. Ullman, Fractional graph theory, Springer-Verlag, New York, 2008.