Boundes for Boxicity of some classes of graphs

Abstract

Let $box(G)$ be the boxicity of a graph $G$, $G[H_1,H_2,\dots ,H_n]$ be the $G$-generalized join graph of $n$-pairwise disjoint graphs $H_1,H_2,\dots ,H_n$, $G_k^d$ be a circular clique graph (where $k\ge 2d$) and $\Gamma (R)$ be the zero-divisor graph of a commutative ring $R$. In this paper, we prove that $\chi (G_k^d)\ge box(G_k^d)$, for all $k$ and $d$ with $k\ge 2d$. This generalizes the results proved in \cite{Aki}. Also we obtain that $box(G[H_1,H_2,\ldots,H_n])\leq \mathop\sum\limits_{i=1}^nbox(H_i)$. As a consequence of this result, we obtain a bound for boxicity of zero-divisor graph of a finite commutative ring with unity. In particular, if $R$ is a finite commutative non-zero reduced ring with unity, then $\chi (\Gamma (R))\le box(\Gamma (R))\le 2^{\chi (\Gamma (R))}-2$. where $\chi (\Gamma (R))$ is the chromatic number of $\Gamma (R)$. Moreover, we show that if $N=\prod _{i=1}^a{p}_i^{2n_i}\prod _{j=1}^b{q}_j^{2m_j+1}$ is a composite number, where $p_i$'s and $q_j$'s are distinct prime numbers, then $box(Γ(\mathbb{Z}_N))\leq \big(\mathop\prod\limits_{i=1}^{a}(2n_i+1)\mathop\prod\limits_{j=1}^{b}(2m_j+2)\big)-\big(\mathop\prod\limits_{i=1}^{a}(n_i+1)\mathop\prod\limits_{j=1}^{b}(m_j+1)\big)-1$, where ${\mathbb{Z}}_N$ is the ring of integers modulo $N$. Further, we prove that, $box(\Gamma ({\mathbb{Z}}_N))=1$ if and only if either $N=p^n$ for some prime number $p$ and some positive integer $n\ge 2$ or $N=2p$ for some odd prime number $p$.