Zero-divisor graph

Short description: Graph of zero divisors of a commutative ring

The zero-divisor graph of [math]\displaystyle{ \mathbb{Z}_2\times\mathbb{Z}_4 }[/math], the only possible zero-divisor graph that is a tree but not a star

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 (Beck 1988), the vertices represent all elements of the ring. In a later variant studied by (Anderson Livingston), the vertices represent only the zero divisors of the given ring.

Examples

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

It is a complete bipartite graph [math]\displaystyle{ K_{p-1,q-1} }[/math] in the case that [math]\displaystyle{ n=pq }[/math] for two distinct prime numbers [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math]. The two sides of the bipartition are the [math]\displaystyle{ p-1 }[/math] nonzero multiples of [math]\displaystyle{ q }[/math] and the [math]\displaystyle{ q-1 }[/math] nonzero multiples of [math]\displaystyle{ p }[/math], respectively. Two numbers (that are not themselves zero modulo [math]\displaystyle{ n }[/math]) multiply to zero modulo [math]\displaystyle{ n }[/math] if and only if one is a multiple of [math]\displaystyle{ p }[/math] and the other is a multiple of [math]\displaystyle{ q }[/math], 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 [math]\displaystyle{ \mathbb{Z}_2\times\mathbb{Z}_4 }[/math].

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 [math]\displaystyle{ d }[/math], the ring has at most [math]\displaystyle{ (d^2-2d+2)^2 }[/math] 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).