Gráfico del divisor de cero

En matemáticas , y más específicamente en álgebra conmutativa combinatoria , un grafo de divisores de cero es un grafo no dirigido que representa los divisores de cero de un anillo conmutativo . Tiene como vértices elementos del anillo y como aristas pares de elementos cuyo producto es cero . ^{[ 1 ]}

Existen dos variantes del grafo de divisores de cero comúnmente utilizadas. En la definición original de Beck (1988) , los vértices representan todos los elementos del anillo. ^{[ 2 ]} En una variante posterior estudiada por Anderson y Livingston (1999) , los vértices representan únicamente los divisores de cero del anillo dado. ^{[ 3 ]}

Si${\displaystyle n}$es un número semiprimo (el producto de dos números primos ) entonces el gráfico del divisor de cero del anillo de enteros módulo${\displaystyle n}$(con solo los divisores de cero como vértices) es un grafo completo o un grafo bipartito completo . Es un grafo completo.${\displaystyle K_{p-1}}$en el caso de que${\displaystyle n=p^{2}}$para algún número primo${\displaystyle p}$En este caso, los vértices son todos los múltiplos no nulos de${\displaystyle p}$y el producto de cualesquiera dos de estos números es cero módulo${\displaystyle p^{2}}$. ^{[ 3 ]}

Es un grafo bipartito completo${\displaystyle K_{p-1,q-1}}$en el caso de que${\displaystyle n=pq}$para dos números primos distintos${\displaystyle p}$y${\displaystyle q}$. Los dos lados de la bipartición son los${\displaystyle p-1}$múltiplos distintos de cero de${\displaystyle q}$y el${\displaystyle q-1}$múltiplos distintos de cero de${\displaystyle p}$, respectivamente. Dos números (que no son en sí mismos cero módulo${\displaystyle n}$) multiplicar a cero módulo${\displaystyle n}$si y solo si uno es múltiplo de${\displaystyle p}$y el otro es un múltiplo de${\displaystyle q}$, por lo que este grafo tiene una arista entre cada par de vértices en lados opuestos de la bipartición, y ninguna otra arista. De manera más general, el grafo divisor de cero es un grafo bipartito completo para cualquier anillo que sea producto de dos dominios de integridad . ^{[ 3 ]}

Los únicos grafos cíclicos que pueden realizarse como grafos de producto cero (con divisores cero como vértices) son los ciclos de longitud 3 o 4. ^{[ 3 ]} Los únicos árboles que pueden realizarse como grafos de divisores cero son las estrellas (grafos bipartitos completos que son árboles) y el árbol de cinco vértices formado como el grafo de divisores cero de${\displaystyle \mathbb {Z} _{2}\times \mathbb {Z} _{4}}$. ^{[ 1 ] [ 3 ]}

En la versión del grafo que incluye todos los elementos, 0 es un vértice universal , y los divisores de cero se pueden identificar como los vértices que tienen un vecino distinto de 0. Debido a que tiene un vértice universal, el grafo de todos los elementos del anillo siempre es conexo y tiene un diámetro como máximo de dos. El grafo de todos los divisores de cero no es vacío para todo anillo que no sea un dominio de integridad . Permanece conexo, tiene un diámetro como máximo de tres, ^{[ 3 ]} y (si contiene un ciclo ) tiene una circunferencia como máximo de cuatro. ^{[ 4 ] [ 5 ]}

El grafo divisor de cero de un anillo que no es un dominio de integridad es finito si y solo si el anillo es finito . ^{[ 3 ]} Más concretamente, si el grafo tiene grado máximo${\displaystyle d}$, el anillo tiene como máximo${\displaystyle (d^{2}-2d+2)^{2}}$elementos. Si el anillo y el grafo son infinitos, cada arista tiene un extremo con infinitos vecinos. ^{[ 1 ]}

Beck (1988) conjeturó que (al igual que los grafos perfectos ) los grafos divisores de cero siempre tienen el mismo número de clique y número cromático . Sin embargo, esto no es cierto; Anderson y Naseer (1993) descubrieron un contraejemplo . ^{[ 6 ]}