ریاضی و جامعه (Dec 2023)
The clique number of the intersection graph of a cyclic group of order with at most three prime factors
Abstract
Let $G$ be a finite non-trivial group. The intersection graph $\Gamma(G)$, is a graph whose vertices are all proper non-trivial subgroups of $G$, and there is an edge between two distinct vertices $H $ and $K$ if and only if $H\cap K\neq 1$. In this paper, we determine the clique number of the intersection graph of the cyclic groups of orders having at most three primes in their decomposition.1. IntroductionLet $G$ be a finite group. There are several ways to associate a graph to $G$ (see [7] and the references therein). The one we will consider in this paper, is denoted by $\Gamma(G)$ and is called the intersection graph of $G$. The intersection graph $\Gamma(G)$ of a nontrivial group $G$ is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper non-trivial subgroups of $G$, and there is an edge between two distinct vertices $H $ and $K$ if and only if $H\cap K\neq 1$ where 1 denotes the trivial subgroup of $G$. The graph $\Gamma(G)$ has been extensively studied ( see, for example, [1, 8, 11, 12]). Currently, the present authors in [4], have determined all groups $G$ such that the clique number of $\Gamma(G)$ is less than 5, and also they have given a criterion for solvability of finite groups $G$, by the clique number of $\Gamma(G)$. More precisely, it has been proved that if $G$ is a finite group such that the clique number of $\Gamma(G)$ is less than 13, then $G$ is solvable. Note that 13 is the clique number of $\Gamma(A_5)$, where $A_5$ is the alternating group on 5 letters. Other researches in this topic are intersection graphs of a semigroup, a module, and ideals of a ring, were investigated in [5], [2] and [6, 10], respectively. 2. Main ResultsWe start this section with the following definition:Definition 2.1. The subset $X$ of vertices of a finite graph $\Gamma$ is called a {\it clique}, if the induced subgraph by $X$ is a complete graph. The maximum size of a clique, among all cliques of $\Gamma$, is called the clique number of $\Gamma$ and we denote it by $\omega(\Gamma)$. If $\Gamma$ is empty (without vertex), then we define $\omega(\Gamma)=0$ and $\omega(\Gamma)=1$ if $\Gamma$ is null (with a non-empty vertex set with no edges). A clique $X$ in $\Gamma$ is called {\it maximal} if there is no clique $Y$ in $\Gamma$ such that $X\subsetneq Y$. Note that the maximum size, among all maximal cliques in $\Gamma(G)$, is $\omega(\Gamma(G))$. To prove the main theorems, we need the following result that its proof can be found in the most valid book of group theory. Proposition 2.2. If $G=\langle g\rangle$ is a cyclic group of ordsr $n$, then for any divisor $s$ of $n$, there is a unique subgroup $H=\langle g^{\frac{n}{s}}\rangle$ of $G$ of order $s$. The following result is a consequence of the above proposition. Corollary 2.3. Let $G$ be a finite cyclic group. Then, the intersection of two proper subgroups of $G$ is non-trivial if and only if their orders are not relatively prime. For a natural number $n$, we denote by $C_n$ the cyclic group of order $n$, $\pi(n)$ the set of prime divisors of $n$ and $d(n)$ the number of all divisors of $n$. Note that if $p$ is a prime number and $n$ is a multiple of $p$, then the number of divisors of $n$ with multiple $p$ is $d(\frac{n}{p})$. If $V(\Gamma(G))$ is the set of vertices of $\Gamma(G)$, then by Proposition 2.2, we have $|V(\Gamma(C_n))|=d(n)-2$. In this paper, we obtain $\omega(\Gamma(C_n))$, where $|\pi(n)|=3$. 3. Summary of Proofs/ConclusionsNow, we state and prove our main results. First, we find the clique number of a cyclic group of a prime power order. Proposition 3.1. If $p$ is a prime and $m$ is a positive integer, then $\omega(\Gamma(C_{p^m}))=m-1$.Proof. Since $|V(\Gamma(C_n))|=d(n)-2$ and $d(p^m)=m+1$, we get the conclusion. In the sequel, assume that $p_1, p_2$ and $p_3$ are distinct primes. Also assume that $n_1, n_2$ and $n_3$ are positive integers such that $n_1\geq n_2\geq n_3$. In the following results, we obtain the clique number of the intersection graph of group $C_{p_1^{n_1}p_2^{n_2}}$. We recall that $d(p_1^{n_1}p_2^{n_2})=(n_1+1)(n_2+1)$. Proposition 3.2. We have$\omega(\Gamma(C_{p_1^{n_1}p_2^{n_2}}))=d(p_1^{n_1}p_2^{n_2})-2-d(p_2^{n_2})=n_1n_2+n_1-1$. Proof. Suppose that $G=C_{p_1^{n_1}p_2^{n_2}}$. Then, we define the subsets of $V(\Gamma(G))$ as follows: ♦ For $1\leq i\leq 2$, $V_{p_i}(\Gamma(G))$ is the set of all proper subgroups $H$ of $G$ such that $\pi(|H|)=\{p_i\}$. ♦ $V_{p_1p_2}(\Gamma(G))$ is the set of all proper subgroups $H$ of $G$ such that $\pi(|H|)=\{p_1, p_2\}$. It is clear that $\{V_{p_1}(\Gamma(G)), V_{p_2}(\Gamma(G)), V_{p_1p_2}(\Gamma(G)) \}$ forms a partition for $V(\Gamma(G))$. By Proposition 2.2, we have $|V_{p_i} (\Gamma(G))|=d(p_i^{n_i})-1=n_i$ and $|V_{p_1p_2}(\Gamma(G))|=d(\frac{n}{p_1p_2})-1=n_1n_2-1$. By Corollary 2.3, in $\Gamma(G)$, each element of the clique $V_{p_1}(\Gamma(G))$ does not join to any element of the clique $V_{p_2}(G)$ and moreover all elements of $V_{p_i}(\Gamma(G))$ for $i=1, 2$ join to all elements of the clique $V_{p_1p_2}(G)$. Therefore $V_{p_1}(\Gamma(G))\cup V_{p_1p_2}(\Gamma(G))$ and $V_{p_2}(\Gamma(G))\cup V_{p_1p_2}(\Gamma(G))$ are the only maximal cliques of $\Gamma(G)$ and since $n_1\geq n_2$, we have the result.Now we state the last main result. Theorem 3.3. Let $G= C_n$ where $n=p_1^{n_1}p_2^{n_2}p_3^{n_3}$. Then\\(1) If $n_1\geq n_2n_3$, then $\omega(\Gamma(G))=d(\frac{n}{p_1})-1=n_1+n_1n_2+n_1n_3+n_1n_2n_3-1$.\\(2) If $n_1\leq n_2n_3$, then $\omega(\Gamma(G))=d(\frac{p_1^{n_1}p_2^{n_2}}{p_1p_2})+d(\frac{p_1^{n_1}p_3^{n_3}}{p_1p_3})+d(\frac{p_2^{n_2}p_3^{n_3}}{p_2p_3})+d(\frac{n}{p_1p_2p_3})-1$\\$$\hspace{5cm}=n_1n_2+n_1n_3+n_2n_3+n_1n_2n_3-1.~~~~~~~~~~~~~~~~~~~~~~~\hspace{4cm}$$Proof. Similar to the proof of Proposition 3.2, we define the subsets of $V(\Gamma(G))$ as follows:\\♦ For $1\leq i\leq 3$, $V_{p_i}(\Gamma(G))$ is the set of all subgroups $H$ of $G$ such that $\pi(|H|)=\{p_i\}$. Therefore, $|V_{p_i}(\Gamma(G))|=d(p_i^{n_i})-1=n_i$.♦ $V_{p_ip_j}(\Gamma(G))$ is the set of all subgroups $H$ of $G$ such that $\pi(|H|)=\{p_i, p_j\}$ for $1\leq i<j\leq 3$. Therefore, $|V_{p_ip_j}(\Gamma(G))|=d(\frac{p_i^{n_i}p_j^{n_j}}{p_ip_j})=n_in_j$where $i\neq j$.♦ $V_{p_1p_2p_3}(\Gamma(G))$ is the set of all proper subgroups $H$ of $G$ such that $\pi(|H|)=\{p_1, p_2, p_3\}$. So, we have$|V_{p_1p_2p_3}(\Gamma(G))|=d(\frac{n}{p_1p_2p_3})-1=n_1n_2n_3-1$.By Proposition 2.2, the above sets forms a partition for $V(\Gamma(G))$. By Corollary 2.3, in $\Gamma(G)$, each element of the clique $V_{p_i}(\Gamma(G))$ does not join to any element of the clique $V_{p_j}(G)\cup V_{p_jp_k}(G)$ for all distinct $i, j, k$ and moreover all elements of $V_{p_i}(\Gamma(G))$ for $i=1, 2, 3$, join to all elements of the clique $V_{p_1p_2p_3}(G)\cup V_{p_ip_j}(G)$, where $1\leq i\neq j\leq 3$. Since $|G|$ has three prime divisors, the intersection of every two subgroups of $G$ of orders with two distinct prime divisors, is non-trivial (by Corollary 2.3). It follows that $V_{p_1p_2}(\Gamma(G))\cup V_{p_1p_3}(\Gamma(G))\cup V_{p_2p_3}(\Gamma(G))$ is a cloque in $\Gamma(G)$. Now, we define $W_i$ as follows for $1\leq i\leq 4$: $$W_1=V_{p_1}(\Gamma(G))\cup V_{p_1p_2}(\Gamma(G))\cup V_{p_1p_3}(\Gamma(G))\cup V_{p_1p_2p_3}(\Gamma(G)), \hspace{0.5cm}|W_1|=n_1+n_1n_2+n_1n_3+n_1n_2n_3-1$$ $$W_2=V_{p_2}(\Gamma(G))\cup V_{p_1p_2}(\Gamma(G))\cup V_{p_2p_3}(\Gamma(G))\cup V_{p_1p_2p_3}(\Gamma(G)), \hspace{0.5cm}|W_2|=n_2+n_1n_2+n_2n_3+n_1n_2n_3-1$$ $$W_3=V_{p_3}(\Gamma(G))\cup V_{p_1p_3}(\Gamma(G))\cup V_{p_2p_3}(\Gamma(G))\cup V_{p_1p_2p_3}(\Gamma(G)), \hspace{0.5cm}|W_3|=n_3+n_1n_3+n_2n_3+n_1n_2n_3-1$$ $$W_4= V_{p_1p_2}(\Gamma(G))\cup V_{p_1p_3}(\Gamma(G))\cup V_{p_2p_3}(\Gamma(G))\cup V_{p_1p_2p_3}(\Gamma(G)), \hspace{0.5cm}|W_4|=n_1n_2+n_1n_3+n_2n_3+n_1n_2n_3-1.$$ It is easy to see that $W_1, W_2, W_3$ and $W_4$ are the only maximal cliques in $\Gamma(G)$. Therefore, $$\omega(\Gamma(G))=max\{|W_1|, |W_2|, |W_3|, |W_4|\}.$$Since $n_1\geq n_2\geq n_3$, we have $|W_1|\geq |W_2|\geq |W_3|$. Thus$$\omega(\Gamma(G))=max\{|W_1|, |W_4|\}=max\{n_1+n_1n_2+n_1n_3+n_1n_2n_3-1, n_1n_2+n_1n_3+n_2n_3+n_1n_2n_3-1\},$$this completes the proof.
Keywords
