El grafo de Gray, de Marion Gray

marion-grayLa 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.

618px-Gray_graph_hamiltonian.svg

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:

Esta entrada participa en la edición 5.6: Paul Erdös del Carnaval de Matemáticas cuyo blog anfitrión es Cifras y teclas.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.




UPV/EHU
ZTF-FCT

Q2006 A2016

facebook facebook

Premio a la Mejor Entrada de marzo del Carnaval de Física 2014: El lago elgygytgyn (por Marta Macho)
Premio Mejor Post en la VII Edición del Carnaval de Humanidades..Gracias a Marta Macho
Premio a la Mejor Entrada de la Edición 4.1231 del Carnaval de Matemáticas.

Egutegia | Calendario

septiembre 2014
L M X J V S D
« Ago   Oct »
1234567
891011121314
15161718192021
22232425262728
2930  

Artxiboak | Archivo

Estatistika | Estadística

  • 4.766.622 sarrerak | visitas

RSS Noticias UPV/EHU

  • Se ha producido un error; es probable que la fuente esté fuera de servicio. Vuelve a intentarlo más tarde.

RSS UPV/EHU Albisteak

  • Se ha producido un error; es probable que la fuente esté fuera de servicio. Vuelve a intentarlo más tarde.

RSS Eventos UPV/EHU

  • Se ha producido un error; es probable que la fuente esté fuera de servicio. Vuelve a intentarlo más tarde.

RSS UPV/EHU Ekitaldiak

  • Se ha producido un error; es probable que la fuente esté fuera de servicio. Vuelve a intentarlo más tarde.
Follow on WordPress.com
Anuncios

A %d blogueros les gusta esto: