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.
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. In a later variant studied by Anderson & Livingston (1999), the vertices represent only the zero divisors of the given ring.
If is a semiprime number (the product of two prime numbers) then the zero-divisor graph of the ring of integers modulo (with only the zero divisors as its vertices) is either a complete graph or a complete bipartite graph. It is a complete graph in the case that for some prime number . For in this case the vertices are all the nonzero multiples of , and the product of any two of these numbers is 0 modulo .
It is a complete bipartite graph in the case that for two distinct prime numbers and . The two sides of the bipartition are the nonzero multiples of and the nonzero multiples of , respectively. Two numbers (that are not themselves zero modulo ) multiply to zero modulo if and only if one is a multiple of and the other is a multiple of , 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.
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. 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 .
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, and (if it contains a cycle) has girth at most four.
The zero-divisor graph of a ring that is not an integral domain is finite if and only if the ring is finite. More concretely, if the graph has maximum degree , the ring has at most elements. If the ring and the graph are infinite, every edge has an endpoint with infinitely many neighbors.
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).
- 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