Una de las alegrías de estar en el comité editorial de una revista de matemáticas de medio pelo es que a veces tengo que encargarme de algún artículo sobre un tema muy específico que me produce una típica reacción WTF: “¿Pero cómo puede ser que alguien trabaje en esto?”. Por suerte, enseguida recuerdo que sólo puede tirar la piedra quien está libre de pecado y lo miro sin prejuicios, y al final termino aprendiendo algo. Esta vez ha sido un artículo sobre una variante de grafos “cordiales”. No había oído hablar en mi vida de ellos y para mi gusto dan para algunos problemas interesantes de competición matemática y poco más. Y en cambio, una búsqueda de las palabras cordial graph en el Google Académico me ha dado 17.400 resultados. Soy un inculto.
El origen de los grafos cordiales está en un problema con un cierto pedigrí en teoría de grafos relacionado con los grafos llamados “gráciles” (graceful en inglés; en castellano los traducen como “graciosos”, por ejemplo en una Matiaventura, pero no creo que sea el sentido original del término). Un grafo no dirigido conexo G=(V,E) con m aristas es grácil cuando admite un etiquetado inyectivo de sus vértices f:V->{0,…,m} tal que si asignamos a cada arista e={u,v} la diferencia en valor absoluto de las etiquetas de sus extremos, |f(u)-f(v)|, obtenemos una biyección entre E y {1,…,m}. En este caso, se dice que el etiquetado f es grácil. Son grafos gráciles los caminos, las estrellas, las orugas, los grafos bipartitos completos, las ruedas y muchos más. Un problema abierto en teoría de grafos con mucho interés es la conjetura de que todos los árboles son gráciles.
El interés de esta conjetura proviene de la famosa Conjetura de G. Ringel de 1963: Dados un grafo completo K de 2n+1 nodos y un árbol T de n+1 nodos, siempre se puede recubrir K con 2n+1 copias de T. Esta conjetura tampoco está resuelta, pero es fácil demostrarla para árboles T gráciles. Si etiquetamos grácilmente los nodos de T con {0,…,n} y etiquetamos los nodos de K con {0,…,2n}, podemos recubrir K con los árboles Tk=(Vk,Ek), k=0,…,2n, donde cada Tk se obtiene sumando k módulo 2n+1 a los nodos de T. Por lo tanto, si todos los árboles son gráciles, la conjetura queda demostrada.
El problema de la existencia de etiquetados gráciles es interesante, e incluso parece ser que tiene aplicaciones en redes de comunicaciones. Y abrió el camino al estudio de otros tipos de etiquetados con propiedades definidas de manera similar. Por ejemplo, en 1980, R. Graham y N. Sloane definieron que un grafo G=(V,E) con m aristas es armonioso cuando admite un etiquetado inyectivo V->Zm tal que si asignamos a cada arista la suma módulo m de las etiquetas de sus extremos obtenemos una biyección entre E y Zm. Su motivación, legítima, fue el estudio de bases aditivas modulares de Zm. Nada que objetar.
Y llegamos a los grafos cordiales, introducidos en 1987 por I. Cahit. Un grafo G es cordial cuando admite un etiquetado f:V->{0,1} tal que
- El número de nodos etiquetados 0 y el de los etiquetados 1 se diferencian en como máximo una unidad
- Si etiquetamos cada arista e=(u,v) con 0 si f(u)= f(v) y con 1 en caso contrario (equivalentemente, con el valor |f(u)-f(v)|, que nos remite a los grafos gráciles, o también con el valor f(u)+f(v) módulo 2, que nos remite a los grafos armoniosos), resulta que el número de aristas etiquetadas 0 y el de las etiquetadas 1 también se diferencian en como máximo una unidad
¿Motivación de esta definición? En palabras de Cahit, “la imposibilidad hasta el momento de demostrar la existencia conjeturada de etiquetados [gráciles o armoniosos] de todos los árboles.” Y es que resulta que es fácil demostrar por inducción completa que todo árbol es cordial, aunque él mismo reconoce que esto no sirve para nada en el contexto de la conjetura de Ringel.
Y luego ya han llegado las generalizaciones por el puro placer de generalizar, del estilo de “un grafo es X-cordial cuando admite un cierto etiquetado f de los nodos tal que si asignamos a cada arista e={u,v} el valor 1 si existe cierta relación X entre f(u) y f(v), y 0 en caso contrario, resulta que el número de aristas etiquetadas 0 y el de las etiquetadas 1 se diferencian en como máximo una unidad”. Poned la relación X que queráis, y ya tenéis una definición para la que demostrar si algunos grafos famosos la cumplen o no, y publicar un artículo en alguna revista con índice de impacto y aumentar el currículum.
En concreto, en los grafos primo-cordiales del artículo que ha motivado este comentario, el etiquetado de los nodos se toma biyectivo en {1,…,|V|} y un arco e={u,v} se etiqueta 1 si mcd(f(u),f(v))=1 y 0 en caso contrario. ¿Interés? ¿Qué queréis que os diga? Como problema de competición matemática, puede tener su gracia pedir si tal grafo famoso es primo-cordial o no, pero no creo que tenga mucho más. Y en cambio, 41 resultados en la búsqueda de las palabras “prime cordial” graph en el Google Académico. Publica o perece en estado puro.
Este artículo participa en la Edición4.1231056256 del Carnaval de Matemáticas, organizado por Cuentos Cuánticos.
el conjunto de los números naturales de n cifras. Para cada 
, sea 
la suma de los n!-1 números que se obtienen permutando sus cifras. La aplicación de 
que envía m a 
Blioquinfo 