- Source: 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 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.
Examples
If
n
{\displaystyle n}
is a semiprime number (the product of two prime numbers)
then the zero-divisor graph of the ring of integers modulo
n
{\displaystyle 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
{\displaystyle K_{p-1}}
in the case that
n
=
p
2
{\displaystyle n=p^{2}}
for some prime number
p
{\displaystyle p}
. In this case the vertices are all the nonzero multiples of
p
{\displaystyle p}
, and the product of any two of these numbers is zero modulo
p
2
{\displaystyle p^{2}}
.
It is a complete bipartite graph
K
p
−
1
,
q
−
1
{\displaystyle K_{p-1,q-1}}
in the case that
n
=
p
q
{\displaystyle n=pq}
for two distinct prime numbers
p
{\displaystyle p}
and
q
{\displaystyle q}
. The two sides of the bipartition are the
p
−
1
{\displaystyle p-1}
nonzero multiples of
q
{\displaystyle q}
and the
q
−
1
{\displaystyle q-1}
nonzero multiples of
p
{\displaystyle p}
, respectively. Two numbers (that are not themselves zero modulo
n
{\displaystyle n}
) multiply to zero modulo
n
{\displaystyle n}
if and only if one is a multiple of
p
{\displaystyle p}
and the other is a multiple of
q
{\displaystyle 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
Z
2
×
Z
4
{\displaystyle \mathbb {Z} _{2}\times \mathbb {Z} _{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
{\displaystyle d}
, the ring has at most
(
d
2
−
2
d
+
2
)
2
{\displaystyle (d^{2}-2d+2)^{2}}
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).