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.

Definition

There are two variations of the zero-divisor graph commonly used.
In the original definition of , the vertices represent all elements of the ring. In a later variant studied by , the vertices represent only the zero divisors of the given ring.

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_$ in the case that $n=p^2$ for some prime number $p$. In this case the vertices are all the nonzero multiples of $p$, and the product of any two of these numbers is zero modulo $p^2$.

It is a complete bipartite graph $K_$ 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.

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 $\mathbb_2\times\mathbb_4$.

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, 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 $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.

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 .

References

{{reflist, refs=

{{citation
, last1 = Anderson , first1 = David F.
, last2 = Axtell , first2 = Michael C.
, last3 = Stickles , first3 = Joe A. Jr.
, contribution = Zero-divisor graphs in commutative rings
, doi = 10.1007/978-1-4419-6990-3_2
, mr = 2762487
, pages = 23–45
, publisher = Springer, New York
, title = Commutative algebra—Noetherian and non-Noetherian perspectives
, year = 2011

{{citation
, last1 = Anderson , first1 = David F.
, last2 = Livingston , first2 = Philip S.
, doi = 10.1006/jabr.1998.7840
, issue = 2
, journal = Journal of Algebra
, mr = 1700509
, pages = 434–447
, title = The zero-divisor graph of a commutative ring
, volume = 217
, year = 1999, doi-access = free

{{citation
, last1 = Anderson , first1 = D. D.
, last2 = Naseer , first2 = M.
, doi = 10.1006/jabr.1993.1171
, issue = 2
, journal = Journal of Algebra
, mr = 1231228
, pages = 500–514
, title = Beck's coloring of a commutative ring
, volume = 159
, year = 1993, doi-access = free

{{citation
, last = Beck , first = István
, doi = 10.1016/0021-8693(88)90202-5
, issue = 1
, journal = Journal of Algebra
, mr = 944156
, pages = 208–226
, title = Coloring of commutative rings
, volume = 116
, year = 1988, doi-access = free

{{citation
, last1 = DeMeyer , first1 = Frank
, last2 = Schneider , first2 = Kim
, contribution = Automorphisms and zero divisor graphs of commutative rings
, mr = 2037656
, pages = 25–37
, publisher = Nova Science , location = Hauppauge, NY
, title = Commutative rings
, year = 2002

{{citation
, last = Mulay , first = S. B.
, doi = 10.1081/AGB-120004502
, issue = 7
, journal = Communications in Algebra
, mr = 1915011
, pages = 3533–3558
, title = Cycles and symmetries of zero-divisors
, volume = 30
, year = 2002

Commutative algebra
Application-specific graphs