Zero-divisor graph

In mathematics, and more specifically in combinatorial commutative algebra, a zero-divisor graph is an undirected graph representing the zero divisors of a commutative ring. It has elements of the ring as its vertices, and pairs of elements whose product is zero as its edges.[1]

The zero-divisor graph of

\mathbb {Z} _{2}\times \mathbb {Z} _{4}

, the only possible zero-divisor graph that is a tree but not a star

Definition

There are two variations of the zero-divisor graph commonly used. In the original definition of Beck (1988), the vertices represent all elements of the ring.[2] In a later variant studied by Anderson & Livingston (1999), the vertices represent only the zero divisors of the given ring.[3]

Examples

If $n$ is a semiprime number (the product of two prime numbers) then the zero-divisor graph of the ring of integers modulo $n$ (with only the zero divisors as its vertices) is either a complete graph or a complete bipartite graph. It is a complete graph $K_{p-1}$ in the case that $n=p^{2}$ for some prime number $p$ . For in this case the vertices are all the nonzero multiples of $p$ , and the product of any two of these numbers is 0 modulo $p^{2}$ .[3]

It is a complete bipartite graph $K_{p-1,q-1}$ in the case that $n=pq$ for two distinct prime numbers $p$ and $q$ . The two sides of the bipartition are the $p-1$ nonzero multiples of $q$ and the $q-1$ nonzero multiples of $p$ , respectively. Two numbers (that are not themselves zero modulo $n$ ) multiply to zero modulo $n$ if and only if one is a multiple of $p$ and the other is a multiple of $q$ , so this graph has an edge between each pair of vertices on opposite sides of the bipartition, and no other edges. More generally, the zero-divisor graph is a complete bipartite graph for any ring that is a product of two integral domains.[3]

The only cycle graphs that can be realized as zero-product graphs (with zero divisors as vertices) are the cycles of length 3 or 4.[3] The only trees that may be realized as zero-divisor graphs are the stars (complete bipartite graphs that are trees) and the five-vertex tree formed as the zero-divisor graph of $\mathbb {Z} _{2}\times \mathbb {Z} _{4}$ .[1][3]

Properties

In the version of the graph that includes all elements, 0 is a universal vertex, and the zero divisors can be identified as the vertices that have a neighbor other than 0. Because it has a universal vertex, the graph of all ring elements is always connected and has diameter at most two. The graph of all zero divisors is non-empty for every ring that is not an integral domain. It remains connected, has diameter at most three,[3] and (if it contains a cycle) has girth at most four.[4][5]

The zero-divisor graph of a ring that is not an integral domain is finite if and only if the ring is finite.[3] More concretely, if the graph has maximum degree $d$ , the ring has at most $(d^{2}-2d+2)^{2}$ elements. If the ring and the graph are infinite, every edge has an endpoint with infinitely many neighbors.[1]

Beck (1988) conjectured that (like the perfect graphs) zero-divisor graphs always have equal clique number and chromatic number. However, this is not true; a counterexample was discovered by Anderson & Naseer (1993).[6]

gollark: My calculator says 6ft is about 180cm. I guess they just like round numbers.

gollark: I could totally sell this if I had more computing power, and also the ability to sell weird products like this to arbitrary companies, and any demand.

gollark: Good idea.

gollark: If you used multiple companies' data you might get accused of something or other.

gollark: Do most boards have enough text message content to make that work?

References

Anderson, David F.; Axtell, Michael C.; Stickles, Joe A., Jr. (2011), "Zero-divisor graphs in commutative rings", Commutative algebra—Noetherian and non-Noetherian perspectives, Springer, New York, pp. 23–45, doi:10.1007/978-1-4419-6990-3_2, MR 2762487
Beck, István (1988), "Coloring of commutative rings", Journal of Algebra, 116 (1): 208–226, doi:10.1016/0021-8693(88)90202-5, MR 0944156
Anderson, David F.; Livingston, Philip S. (1999), "The zero-divisor graph of a commutative ring", Journal of Algebra, 217 (2): 434–447, doi:10.1006/jabr.1998.7840, MR 1700509
Mulay, S. B. (2002), "Cycles and symmetries of zero-divisors", Communications in Algebra, 30 (7): 3533–3558, doi:10.1081/AGB-120004502, MR 1915011
DeMeyer, Frank; Schneider, Kim (2002), "Automorphisms and zero divisor graphs of commutative rings", Commutative rings, Hauppauge, NY: Nova Science, pp. 25–37, MR 2037656
Anderson, D. D.; Naseer, M. (1993), "Beck's coloring of a commutative ring", Journal of Algebra, 159 (2): 500–514, doi:10.1006/jabr.1993.1171, MR 1231228

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[aas-1] Anderson, David F.; Axtell, Michael C.; Stickles, Joe A., Jr. (2011), "Zero-divisor graphs in commutative rings", Commutative algebra—Noetherian and non-Noetherian perspectives, Springer, New York, pp. 23–45, doi:10.1007/978-1-4419-6990-3_2, MR 2762487

[beck-2] Beck, István (1988), "Coloring of commutative rings", Journal of Algebra, 116 (1): 208–226, doi:10.1016/0021-8693(88)90202-5, MR 0944156

[al-3] Anderson, David F.; Livingston, Philip S. (1999), "The zero-divisor graph of a commutative ring", Journal of Algebra, 217 (2): 434–447, doi:10.1006/jabr.1998.7840, MR 1700509

[mulay-4] Mulay, S. B. (2002), "Cycles and symmetries of zero-divisors", Communications in Algebra, 30 (7): 3533–3558, doi:10.1081/AGB-120004502, MR 1915011

[ds-5] DeMeyer, Frank; Schneider, Kim (2002), "Automorphisms and zero divisor graphs of commutative rings", Commutative rings, Hauppauge, NY: Nova Science, pp. 25–37, MR 2037656

[an-6] Anderson, D. D.; Naseer, M. (1993), "Beck's coloring of a commutative ring", Journal of Algebra, 159 (2): 500–514, doi:10.1006/jabr.1993.1171, MR 1231228