L(2,1)-labeling of some zero-divisor graphs associated with commutative rings

Document Type : Original paper

Authors

Department of Mathematics, National Institute of Technology Srinagar

Abstract

Let $\mathcal G = (\mathcal V, \mathcal E)$ be a simple graph, an $L(2,1)$-labeling of $\mathcal G$ is an assignment of labels from non-negative integers to vertices of $\mathcal G$ such that adjacent vertices get labels which differ by at least by two, and vertices which are at distance two from each other get different labels. The $\lambda$-number of $\mathcal G$, denoted by $\lambda(\mathcal G)$, is the smallest positive integer $\ell$ such that $\mathcal G$ has an $L(2,1)$-labeling with all labels as  members of the set $\{ 0, 1, \dots, \ell \}$. The zero-divisor graph of a finite commutative ring $R$ with unity, denoted by $\Gamma(R)$, is the simple graph whose vertices are all zero divisors of $R$ in which two vertices $u$ and $v$ are adjacent  if and only if $uv = 0$ in $R$. In this paper, we investigate $L(2,1)$-labeling of some  zero-divisor graphs. We study the \textit{partite truncation}, a graph operation that allows us to obtain a reduced graph of relatively small order from a graph of significantly larger order. We establish the relation between  $\lambda$-numbers of the graph  and its partite truncated one. We make use of the operation \textit{partite truncation} to contract the zero-divisor graph of a reduced ring to the zero-divisor graph of a Boolean ring.

Keywords

Main Subjects

References

[1] D.F. Anderson, R. Levy, and J. Shapiro, Zero-divisor graphs, von Neumann regular rings, and Boolean algebras, J. Pure Appl. Algebra 180 (2003), no. 3, 221–241.
https://doi.org/10.1016/S0022-4049(02)00250-5
[2] D.F. Anderson and P.S. Livingston, The zero-divisor graph of a commutative ring, J. Algebra 217 (1999), 434–447.
[3] I. Beck, Coloring of commutative rings, J. Algebra 116 (1988), no. 1, 208–226.
https://doi.org/10.1016/0021-8693(88)90202-5
[4] A. Cayley, Desiderata and suggestions: No. 2. the theory of groups: graphical representation, Amer. J. Math. 1 (1878), no. 2, 174–176.
https://doi.org/10.2307/2369306
[5] I. Chakrabarty, S. Ghosh, and M.K. Sen, Undirected power graphs of semigroups, Semigroup Forum, vol. 78, Springer, 2009, pp. 410–426.
https://doi.org/10.1007/s00233-008-9132-y
[6] F. DeMeyer and L. DeMeyer, Zero divisor graphs of semigroups, J. Algebra 283 (2005), no. 1, 190–198.
https://doi.org/10.1016/j.jalgebra.2004.08.028
[7] J.P. Georges and D.W. Mauro, On regular graphs optimally labeled with a condition at distance two, SIAM J. Discrete Math. 17 (2003), no. 2, 320–331.
https://doi.org/10.1137/S0895480101391247
[8] J.P. Georges, D.W. Mauro, and M.A. Whittlesey, Relating path coverings to vertex labellings with a condition at distance two, Discrete Math. 135 (1994), no. 1–3, 103–111.
https://doi.org/10.1016/0012-365X(93)E0098-O
[9] J. Griggs and R. Yeh, Labelling graphs with a condition at distance two, SIAM J. Discrete Math. 5 (1992), no. 4, 586–595.
https://doi.org/10.1137/0405048
[10] A. Kelarev, C. Ras, and S. Zhou, Distance labellings of Cayley graphs of semigroups, Semigroup Forum, vol. 91, Springer, 2015, pp. 611–624.
https://doi.org/10.1007/s00233-015-9748-7
[11] A.V. Kelarev and S.J. Quinn, A combinatorial property and power graphs of groups, Contributions to General Algebra 12 (2000), no. 58, 3–6.
[12] B.M. Kim, Y. Rho, and B.C. Song, Lambda number for the direct product of some family of graphs, J. Comb. Optim. 33 (2017), 1257–1265.
https://doi.org/10.1007/s10878-016-0032-x
[13] X. Ma, M. Feng, and K. Wang, Lambda number of the power graph of a finite group, J. Algebraic Combin. 53 (2021), 743–754.
https://doi.org/10.1007/s10801-020-00940-9
[14] E. Mazumdar and R. Raja, Group-annihilator graphs realised by finite abelian groups and its properties, Graphs Combin. 38 (2022), Article numbe: 25.
https://doi.org/10.1007/s00373-021-02422-6
[15] K. M¨onius, Eigenvalues of zero-divisor graphs of finite commutative rings, J. Algebraic Combin. 54 (2021), 787–802.
https://doi.org/10.1007/s10801-020-00989-6
[16] S. Pirzada, B.A. Rather, M. Aijaz, and T.A. Chishti, On distance signless Laplacian spectrum of graphs and spectrum of zero divisor graphs of Zn, Linear Multilinear Algebra 70 (2022), no. 17, 3354–3369.
https://doi.org/10.1080/03081087.2020.1838425
[17] S. Pirzada and S.A. Rather, On the linear strand of edge ideals of some zerodivisor graphs, Comm. Algebra 51 (2023), no. 2, 620–632.
https://doi.org/10.1080/00927872.2022.2107211
[18] R. Raja, Total perfect codes in graphs realized by commutative rings, Trans. Comb. 11 (2022), no. 4, 295–307.
https://doi.org/10.22108/toc.2021.122946.1727
[19] B.A. Rather, S. Pirzada, T.A. Naikoo, and Y. Shang, On Laplacian eigenvalues of the zero-divisor graph associated to the ring of integers modulo $n$, Mathematics 9 (2021), no. 5, Article number: 482.
https://doi.org/10.3390/math9050482
[20] F.S. Roberts, T-colorings of graphs: recent results and open problems, Discrete Math. 93 (1991), no. 2-3, 229–245.
https://doi.org/10.1016/0012-365X(91)90258-4
[21] M.A. Whittlesey, J.P. Georges, and D.W. Mauro, On the $\lambda$-number of $Q_n$ and related graphs, SIAM J. Discrete Math. 8 (1995), no. 4, 499–506.
https://doi.org/10.1137/S0895480192242821
[22] S. Zahirović, The power graph of a torsion-free group determines the directed power graph, Discrete Appl. Math. 305 (2021), 109–118.
https://doi.org/10.1016/j.dam.2021.08.028
[23] S. Zhou, Labelling Cayley graphs on abelian groups, SIAM J. Discrete Math. 19 (2005), no. 4, 985–1003.
https://doi.org/10.1137/S0895480102404458
 
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 25 November 2023

Files

Share

How to cite

Statistics