Total perfect codes in graphs realized by commutative rings

Document Type : Research Paper


Department of Mathematics, National Institute of Technology, Hazratbal-190006, Srinagar, India


Let $R$ be a commutative ring with unity not equal to zero and let $\Gamma(R)$ be a zero-divisor graph realized by $R$. For a simple, undirected, connected graph $G = (V, E)$, a {\it total perfect code} denoted by $C(G)$ in $G$ is a subset $C(G) \subseteq V(G)$ such that $|N(v) \cap C(G)| = 1$ for all $v \in V(G)$, where $N(v)$ denotes the open neighbourhood of a vertex $v$ in $G$. In this paper, we study total perfect codes in graphs which are realized as zero-divisor graphs. We show a zero-divisor graph realized by a local commutative ring with unity admits a total perfect code if and only if the graph has degree one vertices. We also show that if $\Gamma(R)$ is a regular graph on $|Z^*(R)|$ number of vertices, then $R$ is a reduced ring and $|Z^*(R)| \equiv 0 (mod ~2)$, where $Z^*(R)$ is a set of non-zero zero-divisors of $R$. We provide a characterization for all commutative rings with unity of which the realized zero-divisor graphs admit total perfect codes. Finally, we determine the cardinality of a total perfect code in $\Gamma(R)$ and discuss the significance of the study of total perfect codes in graphs realized by commutative rings with unity.


Main Subjects

[1] D. F. Anderson and P. S. Livingston, The zero-divisor graph of a commutative ring, J. Algebra, 217 (1999) 434–447.
[2] D. F. Anderson, R. Levy and J. Shapiro, Zero-divisor graphs, von Neumann regular rings, and Boolean algebras, J.
Pure Appl. Algebra, 180 (2003) 221–241.
[3] C. Araujo and I. Dejter, Lattice-like total perfect codes, Discuss. Math. Graph Theory, 34 no. 1 (2014) 57–74.
[4] I. Beck, Coloring of commutative rings, J. Algebra, 116 (1988) 208–226.
[5] N. L. Biggs, Perfect codes in graphs, J. Combin. Theory Ser. B, 15 (1973) 289 –296.
[6] P. J. Cameron, S. E. Payne and J. A. Thas, Polarities of generalized hexagons and perfect codes, Geom. Dedicata,
5 (1976) 525–528.
[7] G. Chang, C. Rangan and S. Coorg, Weighted Independent Perfect Domination on Cocomparability Graphs, Disc.
Appl. Math., 63 (1995) 215– 223.
[8] P. Cull and I. Nelson, Error-correcting codes on the Towers of Hanoi graphs, Disc. Math., 208/209 (1999) 157–175.
[9] I. J. Dejtera and O. Serra, Efficient dominating sets in Cayley graphs, Disc. Appl. Math., 129 (2003) 319–328.
[10] M. Dorfling, W. Goddard, M. A. Henning, and C. M. Mynhardt Construction of trees and graphs with equal
domination parameters, Disc. Math., 306 no. 21 (2006) 2647–2654.
[11] H. Gavlas, K. Schultz, and P. Slater. Efficient open domination in graphs. Sci. Ser. A Math. Sci., 6 (2003) 77–84.
[12] M. J. E. Golay, Notes on digital coding, Proc. IEEE, 37 (1949) p. 657.
[13] A-A. Ghidewon, R. H. Hammack and D. T. Taylor, Total perfect codes in tensor products of graphs, Ars Combin.,
88 (2008) 129–134.
[14] R. W. Hamming, Error detecting and error correcting codes, Bell Syst. Tech. J., 29 (1950) 147–160.
[15] P. Hammond, q-Coverings, Codes and Line Graphs, J. Combin.Theory Ser. B, 30 (1981) 32–35.
[16] J. H. Hattingh and M. A. Henning. Characterizations of trees with equal domination parameters, Journal of Graph
Theory, 34 no. 2 (2000) 142–153.
[17] T. W. Haynes, S. T. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New
York, (1998).
[18] M. A. Henning, A characterization of roman trees, Discuss. Math. Graph Theory, 22 no. 2 (2002) 325–334.
[19] S. Klavzar, U. Milutinovic and C. Petr, 1-Perfect codes in Sierpinski graphs, Bull. Austral. Math. Soc., 66 (2002)
[20] M. Knor and P. Potocnik, Efficient domination in cubic vertex-transitive graphs, European J. Combin., 33 no. 8
(2012) 1755–1764.
[21] J. Kratochvil, Perfect codes over graphs, J. Combin. Theory Ser. B, 40 no. 2 (1986) 224–228.
[22] J. Lee, Independent perfect domination sets in Cayley graphs, J. Graph Theory, 37 (2001) 213–219.
[23] M. Livingstone and Q. Stout, Perfect Dominating Sets, Cong. Num., 79 (1990) 187–203.
[24] S. Pirzada and Rameez Raja, On graphs associated with modules over commutative rings, J. Korean. Math. Soc.,
53 no. 5 (2016) 1167–1182.
[25] S. Pirzada and Rameez Raja, On the metric dimension of a zero-divisor graph, Commun. Algebra, 45 no. 4 (2017)
[26] Rameez Raja, S. Pirzada and S. P. Redmond, On Locating numbers and codes of zero-divisor graphs associated
with commutative rings, J. Algebra Appl., 15 no. 1 (2016) 1650014 pp. 22.
[27] S. P. Redmond, The zero-divisor graph of a non-commutative ring, Internat. J. Commutative Rings, 1 no. 4 (2002)
[28] S. P. Redmond, An ideal-based zero-divisor graph of a commutative ring, Commun. Algebra, 31 (2003) 4425–4443.
[29] S. P. Redmond, Cut vertices and Degree one vertices of zero-divisor graphs, Commun. Algebra, 40 no. 8 (2012)
[30] S. P. Redmond, On zero-divisor graphs of small finite commutative rings, Disc. Math., 307 (2007) 1155–1166.
[31] P. Slater. A constructive characterization of trees with at least k disjoint maximum matchings, Journal of Combin.
Theory Ser. B, 25 (1978) 326–338.
[32] J. A. Thas, Two infinite classes of perfect codes in metrically regular graphs, J. Combin. Theory Ser. B, 23 (1977)
[33] J. H. van Lint, A survey of perfect codes, Rocky Mountain J. Math., 5 (1975) 199–224.
[34] S. Zhou, Total perfect codes in Cayley graphs, Des. Codes Cryptogr., 18 no. 3 (2016) 489–504.