Zero-divisor graph

{{Short description|Graph of zero divisors of a commutative ring}}

File:Zero-divisor graph of Z2xZ4.svg of $\mathbb{Z}_2\times\mathbb{Z}_4$ , 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.{{r|aas}}

Definition

There are two variations of the zero-divisor graph commonly used.

In the original definition of {{harvtxt|Beck|1988}}, the vertices represent all elements of the ring.{{r|beck}} In a later variant studied by {{harvtxt|Anderson|Livingston|1999}}, the vertices represent only the zero divisors of the given ring.{{r|al}}

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$ . 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$ .{{r|al}}

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.{{r|al}}

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.{{r|al}}

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$ .{{r|aas|al}}

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,{{r|al}} and (if it contains a cycle) has girth at most four.{{r|mulay|ds}}

The zero-divisor graph of a ring that is not an integral domain is finite if and only if the ring is finite.{{r|al}} 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.{{r|aas}}

{{harvtxt|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 {{harvtxt|Anderson|Naseer|1993}}.{{r|an}}

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}}

}}

Category:Commutative algebra

Category:Application-specific graphs