El grafo de Gray, de Marion Gray |

La matemática Marion Gray (1902-1979) falleció un 16 de septiembre.

Defendió su tesis doctoral en 1926 –The theory of singular ordinary differential equations of the second order– supervisada por Anna Wheeler en Bryn Mawr College (EE.UU.).

Estuvo vinculada durante una temporada a la University of Edinburgh y el Imperial College de Londres, y en 1930 comenzó a trabajar en el Departamento de Desarrollo e Investigación de la American Telephone and Telegraph Company de Nueva York. Allí, descubrió el grafo que lleva su nombre (1932), un grafo cúbico con 54 vértices y 81 aristas.

I. Z. Bouwer fue el primero en publicar sobre este tema [An edge but not vertex transitive cubic graph, Bulletin of the Canadian Mathematical Society 11 (1968) 533–535]: Gray no publicó su descubrimiento, y treinta y seis años más tarde Bouwer redescubrió el grafo y escribió sobre sus propiedades de simetría.

El diámetro –la excentricidad maximal de sus vértices– del grafo de Gray es 6, su radio –la excentricidad maximal de sus vértices–es 6, y su circunferencia –la longitud de su ciclo mas corto– es 8. Es un grafo conexo, y para desconectarlo, es preciso eliminar como mínimo tres vértices o tres aristas.

Este grafo es además semi-simétrico (fue Bouwer quien lo probó en su artículo de 1968) es decir,

es arista-transitivo –existe un automorfismo del grafo que lleva cualquier arista en otra–,
regular –todos los vértices tienen el mismo grado–,
y no es vértice-transitivo –no existe un automorfismo del grafo que lleva cualquier vértice en otro–.

Además es el menor grafo cúbico semi-simétrico [A. Malnič, D. Marušič, P. Potočnik & C. Wang, An infinite family of cubic edge- but not vertex-transitive graphs, Discr. Math. 280 (2002) 133-148].

Este grafo, y otros similares, es fundamental en teoría de redes.

Más información: