Zero-divisor graph

<h2 id="definition">Definition</h2>
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.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> In a later variant studied by Anderson & Livingston (1999), the vertices represent only the <a href="/facts/Zero_divisor/5GraAU8o">zero divisors</a> of the given ring.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

<h2 id="examples">Examples</h2>
If 
 
 
 
 n
 
 
 {\displaystyle n}
 
 is a <a href="/facts/Semiprime_number/J5cNFs7T">semiprime number</a> (the product of two <a href="/facts/Prime_number/L20FLkgn">prime numbers</a>)
then the zero-divisor graph of the ring of <a href="/facts/Integer/PUwwrawx">integers</a> <a href="/facts/Modular_arithmetic/0wtRa5dU">modulo</a> 
 
 
 
 n
 
 
 {\displaystyle n}
 
 (with only the zero divisors as its vertices) is either a <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> or a <a href="/facts/Complete_bipartite_graph/C1RYIdpX">complete bipartite graph</a>.
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}}
 
.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
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}
 
 <a href="/facts/If_and_only_if/bYSxGJ66">if and only if</a> 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 <a href="/facts/Product_ring/wBGSEE54">product</a> of two <a href="/facts/Integral_domain/cylt6zxW">integral domains</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
The only <a href="/facts/Cycle_graph/bYhnPDHc">cycle graphs</a> that can be realized as zero-product graphs (with zero divisors as vertices) are the cycles of length 3 or 4.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
The only <a href="/facts/Tree_(graph_theory)/TCWk4Joy">trees</a> that may be realized as zero-divisor graphs are the <a href="/facts/Star_(graph_theory)/PNW0H6eK">stars</a> (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}}
 
.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a><a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

<h2 id="properties">Properties</h2>
In the version of the graph that includes all elements, 0 is a <a href="/facts/Universal_vertex/5YRHn7Y2">universal vertex</a>, 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 <a href="/facts/Connectivity_(graph_theory)/FSNjsYhz">connected</a> and has <a href="/facts/Diameter_(graph_theory)/EmQFKvqa">diameter</a> at most two. The graph of all zero divisors is non-empty for every ring that is not an <a href="/facts/Integral_domain/cylt6zxW">integral domain</a>. It remains connected, has diameter at most three,<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> and (if it contains a <a href="/facts/Cycle_(graph_theory)/Is44edrv">cycle</a>) has <a href="/facts/Girth_(graph_theory)/rPwRGgxj">girth</a> at most four.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a><a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>
The zero-divisor graph of a ring that is not an integral domain is finite if and only if the ring is <a href="/facts/Finite_ring/9paodazt">finite</a>.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> More concretely, if the graph has maximum <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> 
 
 
 
 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.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>
Beck (1988) <a href="/facts/Conjecture/oPWUb7SF">conjectured</a> that (like the <a href="/facts/Perfect_graph/wcPdhjG9">perfect graphs</a>) zero-divisor graphs always have equal <a href="/facts/Clique_number/XK9ppLz5">clique number</a> and <a href="/facts/Chromatic_number/J6HoBfP0">chromatic number</a>. However, this is not true; a <a href="/facts/Counterexample/dnThYpHW">counterexample</a> was discovered by Anderson & Naseer (1993).<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Anderson, David F.; Axtell, Michael C.; Stickles, Joe A. Jr. (2011), "Zero-divisor graphs in commutative rings", Commutative algebra—Noetherian and non-Noetherian perspectives, Springer, New York, pp. 23–45, doi:10.1007/978-1-4419-6990-3_2, MR 2762487 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Beck, István (1988), "Coloring of commutative rings", Journal of Algebra, 116 (1): 208–226, doi:10.1016/0021-8693(88)90202-5, MR 0944156 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Anderson, David F.; Livingston, Philip S. (1999), "The zero-divisor graph of a commutative ring", Journal of Algebra, 217 (2): 434–447, doi:10.1006/jabr.1998.7840, MR 1700509 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Anderson, David F.; Livingston, Philip S. (1999), "The zero-divisor graph of a commutative ring", Journal of Algebra, 217 (2): 434–447, doi:10.1006/jabr.1998.7840, MR 1700509 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Anderson, David F.; Livingston, Philip S. (1999), "The zero-divisor graph of a commutative ring", Journal of Algebra, 217 (2): 434–447, doi:10.1006/jabr.1998.7840, MR 1700509 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Anderson, David F.; Livingston, Philip S. (1999), "The zero-divisor graph of a commutative ring", Journal of Algebra, 217 (2): 434–447, doi:10.1006/jabr.1998.7840, MR 1700509 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Anderson, David F.; Axtell, Michael C.; Stickles, Joe A. Jr. (2011), "Zero-divisor graphs in commutative rings", Commutative algebra—Noetherian and non-Noetherian perspectives, Springer, New York, pp. 23–45, doi:10.1007/978-1-4419-6990-3_2, MR 2762487 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Anderson, David F.; Livingston, Philip S. (1999), "The zero-divisor graph of a commutative ring", Journal of Algebra, 217 (2): 434–447, doi:10.1006/jabr.1998.7840, MR 1700509 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Anderson, David F.; Livingston, Philip S. (1999), "The zero-divisor graph of a commutative ring", Journal of Algebra, 217 (2): 434–447, doi:10.1006/jabr.1998.7840, MR 1700509 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Mulay, S. B. (2002), "Cycles and symmetries of zero-divisors", Communications in Algebra, 30 (7): 3533–3558, doi:10.1081/AGB-120004502, MR 1915011 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">DeMeyer, Frank; Schneider, Kim (2002), "Automorphisms and zero divisor graphs of commutative rings", Commutative rings, Hauppauge, NY: Nova Science, pp. 25–37, MR 2037656 <a href="/wiki/MR_(identifier)" target="_blank">/wiki/MR_(identifier)</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Anderson, David F.; Livingston, Philip S. (1999), "The zero-divisor graph of a commutative ring", Journal of Algebra, 217 (2): 434–447, doi:10.1006/jabr.1998.7840, MR 1700509 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Anderson, David F.; Axtell, Michael C.; Stickles, Joe A. Jr. (2011), "Zero-divisor graphs in commutative rings", Commutative algebra—Noetherian and non-Noetherian perspectives, Springer, New York, pp. 23–45, doi:10.1007/978-1-4419-6990-3_2, MR 2762487 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Anderson, D. D.; Naseer, M. (1993), "Beck's coloring of a commutative ring", Journal of Algebra, 159 (2): 500–514, doi:10.1006/jabr.1993.1171, MR 1231228 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
</ol>

Zero-divisor graph open-in-new

Zero-divisor graph