Buscando Recursos para Identificar el Nombre de un Gráfico Dado

Question

A veces específicos gráficos tienen muy agradable propiedades y tienden a aparecer con la suficiente frecuencia que se les ha dado nombres como el Gráfico de Petersen, la Torre del Gráfico, el de Durero Gráfico, etc. Es allí cualquier manera conveniente para "buscar" un gráfico sin saber su nombre con el fin de averiguar si tiene un nombre? Sería agradable si había algo menos tedioso que mirando por encima de las listas de gráficos (que parecía ser la única opción que se menciona en esta pregunta), o tratando de determinar las propiedades de un gráfico y, a continuación, buscar en Google esas propiedades.

WolframAlpha parece el candidato más probable, pero a veces cuando entro en el edgelist. Y parece un poco ineficiente para hacer un "Lo que este Gráfico" publicar en MathSE cuando este sube.

---

Si alguien quiere el reto específico, el gráfico actual en cuestión es el siguiente $6$-gráfico regular con $10$ vértices y $30$ bordes. Este gráfico ($G$) tiene la propiedad de que para cualquier par de vértices $v_1$,$v_2$ los gráficos de $G-v_1$ $G-v_2$ son isomorfos. Del mismo modo $G-e_1$ $G-e_2$ son isomorfos para cualquiera de los dos bordes. Estoy bastante seguro de que esto implica que la gráfica es simétrica. $$ \left\{(1,3),(1,4),(1,6),(1,7),(1,9),(1,10),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(3,5),(3,6),(3,8),(3,9),(3,10),(4,6),(4,7),(4,8),(4,10),(5,7),(5,8),(5,9),(5,10),(6,8),(6,9),(7,9),(7,10),(8,10)\right\} $$

El trabajo realizado en esta página se muestra que existen $21$ $6$-regular los gráficos en $10$ vértices, por lo que mi gráfica no puede ser tan especial como yo pensaba y no puede tener un nombre.

Answer 1

Es el 5-triangular gráfico. También llamado el (5,2)-Johnson gráfico. He utilizado Mathematica, que tiene un índice de gráficos, y encontró que el 10 vértices, de 30 de borde simétrico de los gráficos. A continuación, he calculado el espectro / polinomio característico de su gráfica para comprobar la coincidencia.

Oh-y complemento de la Petersen gráfico. Debería haber empezado por tomar el complemento de todos modos, pero yo ya había encontrado por ese punto. Si el doble de la de valencia supera el número de vértices, mira el gráfico complemento de la primera.

---

Para proporcionar un par de fragmentos de código, la función GraphData[] se utiliza para acceder al índice de gráficos disponibles en Mathematica. Para seleccionar los nombres de todos los simétrica gráficos con $10$ vértices y $30$ bordes en el índice, se podría usar el siguiente código que devuelve sólo el $5$-triangular gráfico:

Select[GraphData["Symmetric", 10], GraphData[#, "EdgeCount"] == 30 &]

Para más directamente a responder a la pregunta, si usted acaba de tener el edgelist de un gráfico y quieres buscar en el índice (y no quieres complicarte el cálculo de cualquiera de las propiedades del gráfico), podría usar este:

g = Graph[(* EDGELIST *)];
Select[GraphData[], IsomorphicGraphQ[GraphData[#], g] &]

Esta última línea es bastante lento, pero puede ser acelerado considerablemente mediante la adición de un par de condiciones en el primer GraphData[].