Grafos e divisores.2

Nunha entrada anterior chegamos á idea de grafo de divisores de forma natural, como ferramenta para abordaxe do estudo da lonxitude dos camiños nun xogo de múltiplos e divisores que recolliamos da páxina Nrich. Así, dado o conxunto S dos n primeiros números naturais construiamos un grafo de tal xeito que se $$i,j\in S\quad \quad \quad ij\quad é\quad unha\quad aresta\quad \Longleftrightarrow \quad i|j\quad ou\quad j|i$$
O concepto de grafo de divisores pódese ampliar tomando S como calquer subconxunto finito de números enteiros. Con esta nova definición resulta que temos moitos grafos que son grafos de divisores. Por exemplo todos os posibles grafos con 5 vértices ou menos, agás un, son grafos de divisores. Non é nada complicado debuxalos todos asignándolle os números correspondentes aos vértices para comprobar que realmente son grafos de divisores. Velaquí uns poucos de exemplos (a comprobación da totalidade deles pode ser un exercicio divertido)

Unha actividade entretida para os que teñan algo de gosto pola astronomía podía ser o de indagar se as constelacións son grafos de divisores. Velaquí, por exemplo que o Setestrelo sí que o é:Se temos n vértices, o maior número de arestas que podemos establecer entre eles é un deses problemas que se resolven nas primeiras clases de combinatoria:

 son $$\left( \begin{matrix} n \\ 2 \end{matrix} \right) $$.
Tendo isto presente, verifícase o seguinte teorema:
$$Dados\quad dous\quad números\quad naturais,\quad n\quad e\quad m,\quad con\quad 0\le m\le \left( \begin{matrix} n \\ 2 \end{matrix} \right) ,\quad \\ hai\quad polo\quad menos\quad un\quad grafo\quad divisor\quad con\quad n\quad vértices\quad e\quad m\quad arestas$$

Este resultado asegura certa abundancia de grafos divisores. Tamén se sabe que todos os grafos completos K_n , K_m,n ,  as árbores e todos os grafos bipartitos son grafos de divisores. Pero tamén hai moitos outros grafos que non son divisores. O grafo cíclico C₅ non é un grafo divisor, incluso máis, ningún grafo divisor pode conter a C₅. A razón de que isto sexa así vén da transitividade da relación "ser divisor de". Así, todo grafo divisor ten asociado un grafo dirixido no que se u|v podemos establecer un arco (u,v). Se C₅ fose un grafo divisor, tería que haber tres vértices x, y, z, tales que x|y e y|z. Polo tanto x|z e debería haber unha aresta máis que as que ten C₅. De feito, ningún grafo cíclico impar de 5 ou máis vértices, pode ser un grafo divisor.

Pola contra é moi doado establecer un algoritmo que asigne valores numéricos aos vértices co fin de converter en grafos divisores todos os cíclicos pares.  Para comprobarmos que por exemplo C₆ é un grafo de divisores basta ir etiquetando, poñamos por caso, no sentido das agullas dun reloxo, un vértice si e outro non, cos primeiros primos: 2, 3, 5,.... Os vértices intermedios serán o produto dos dous adxacentes. Está claro que a paridade é o que determina que poidamos realizar esta etiquetaxe nun grafo cíclico.
Xa sabemos que C₅ non é grafo de divisores. Podemos dar referencia de moitos máis. Velaquí un par de exemplos:

Entón xurde a cuestión de caracterizar os grafos divisores. Xa sabemos que a todo grafo de divisores vaille asociado un grafo dirixido. Basta escoller os arcos a partir da relación "u divide a v". Daquela temos o seguinte resultado:

Que un grafo sexa un grafo de divisores é equivalente a que exista unha orientación que verifique a propiedade transitva [isto é, se (u,v) e (v,w) son arcos, entón (u,w) tamén o será]

Xeneralizando
Pódese ampliar novamente o concepto de grafo divisor. No canto de considerar o conxunto dos números enteiros podemos tomar un anel conmutativo calquera.
Neste contexto vai unha cuestión. Sexa K₅ o grafo completo de 5 vértices. Será un grafo de divisores? Para abordar a pregunta pensei que se podería resolver se tiñamos un anel con 5 unidades.
Sexa
$$\xi ={ e }^{ \frac { 2\pi i }{ 5 }  }=cos\frac { 2\pi  }{ 5 } +i\cdot sen\frac { 2\pi  }{ 5 }  $$ a raíz quinta da unidade. Resulta que o anel ciclotómico $$Z\left[ \xi  \right] $$ ten como unidades $$1,\xi ,{ \xi  }^{ 2 },{ \xi  }^{ 3 },{ \xi  }^{ 4 }$$ polo que o grafo divisor asociado ao conxunto destes cinco elementos é o grafo completo K₅.
Despois de pegar este chimpo vin que se podía chegar ao mesmo resultado cun grafo en Z, tomando o conxunto de vértices $$S=\left\{ 2,{ 2 }^{ 2 },{ 2 }^{ 3 },{ 2 }^{ 4 },{ 2 }^{ 5 } \right\} $$
Está claro que todos os grafos completos son divisores. A cuestión que me asaltou é se hai algún anel que dea acubillo a algún grafo divisor que non poidamos atopar en Z.

Máis?
Un concepto asociado ao dos grafos divisores é o dos grafos coprimos. Considerando o conxunto de vértices entre os enteiros, as arestas (u,v) estableceranse entre aqueles números que sexan coprimos.
Dada un grafo G calquera, seguindo o seguinte procedemento, obteremos un grafo coprimo isomorfo a G:

• Consideremos o grafo complementario G cos mesmos vértices e cuxas arestas son xusto as que non aparecen en G
• En G etiquetamos todos os vértices aillados con números primos (distintos)
• Se temos unha aresta aillada en G escolleremos outro primo p e etiquetaremos os dous vértices como p e p²
• Se temos unha compoñente de orde 3 ou más en G, asociaremos primos distintos a cada unha das súas arestas. Entón cada vértice etiquétase co produto das arestas que inciden nel.

Deste xeito podemos construir un grafo coprimo isomorfo a calquera outro dado: todos os grafos son grafos coprimos. Velaquí, como exemplo, temos o proceso de etiquetaxe de C₅.

Algunhas lecturas
Whic graphs are divisor graphs?
Bipartite divisor graphs
Divisor graph have arbitrary order and size
On the logest simple paht in a divisor graph
Further new properties of divisor graphs