In mathematics, and more specifically in

combinatorial commutative algebra Combinatorial commutative algebra is a relatively new, rapidly developing mathematical discipline. As the name implies, it lies at the intersection of two more established fields, commutative algebra and combinatorics, and frequently uses methods o ...

, a zero-divisor graph is an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

representing the

zero divisor In abstract algebra, an element of a ring is called a left zero divisor if there exists a nonzero in such that , or equivalently if the map from to that sends to is not injective. Similarly, an element of a ring is called a right zero ...

s of a

commutative ring In mathematics, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring properties that are not sp ...

. 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

s of the given ring.

Examples

n

is a

semiprime number In mathematics, a semiprime is a natural number that is the product of exactly two prime numbers. The two primes in the product may equal each other, so the semiprimes include the squares of prime numbers. Because there are infinitely many prime nu ...

(the product of two

prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...

s) 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 In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...

or a

complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory ...

. 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 0 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 Product may refer to: Business * Product (business), an item that serves as a solution to a specific consumer problem. * Product (project management), a deliverable or set of deliverables that contribute to a business solution Mathematics * Produ ...

of two

integral domain In mathematics, specifically abstract algebra, an integral domain is a nonzero commutative ring in which the product of any two nonzero elements is nonzero. Integral domains are generalizations of the ring of integers and provide a natural set ...

s. The only

cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...

s that can be realized as zero-product graphs (with zero divisors as vertices) are the cycles of length 3 or 4. The only

trees In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...

that may be realized as zero-divisor graphs are the

stars A star is an astronomical object comprising a luminous spheroid of plasma held together by its gravity. The nearest star to Earth is the Sun. Many other stars are visible to the naked eye at night, but their immense distances from Earth ma ...

(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 In graph theory, a universal vertex is a vertex of an undirected graph that is adjacent to all other vertices of the graph. It may also be called a dominating vertex, as it forms a one-element dominating set in the graph. (It is not to be confused ...

, 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

. It remains connected, has diameter at most three, and (if it contains a cycle) has

girth Girth may refer to: ;Mathematics * Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space * Girth (geometry), the perimeter of a parallel projection of a shape * 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 graph In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph (clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is perfec ...

s) zero-divisor graphs always have equal

clique number In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is compl ...

and

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

. 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