La eliminación de bordes no isomórficos da como resultado el mismo gráfico

Question

Existe una simple (sin etiqueta) gráfico 6 nodos con un par de no-isomorfo bordes (es decir, no hay ningún gráfico automorphism que envía una orilla a la otra) de forma tal que la eliminación de cualquiera de ellos resulta en el mismo gráfico:

Los dos no isomorfos bordes de aquí son de color rojo y azul. Este es el más pequeño ejemplo de este tipo de gráfico y es único por 6 nodos.

Me pregunto cuál sería el más pequeño ejemplo de una gráfica con un triple de pares no isomorfos de los bordes y la eliminación de cualquiera de ellos, lo que produce en el mismo gráfico.

P. S. Véase también la secuencia https://oeis.org/A245246 -- extensión es bienvenido.

ACTUALIZACIÓN: user2097 a continuación dio una construcción de una gráfica en la $(\tbinom{n}{2}+1)\cdot n$ nodos que las plazas el número de pares no isomorfos de los bordes. Cuando se aplica para el mencionado gráfico 6 nodos, se da una gráfica de 96 nodos con un cuádruple de pares no isomorfos de los bordes, la eliminación de cada una de las cuales produce el mismo gráfico. Pero probablemente no es el más pequeño de tales gráfico.

Answer 1

Esto es esencialmente un comentario en user2097 excelente respuesta. Una de las consecuencias de esa respuesta fue la construcción de un gráfico con cuatro no isomorfos bordes cuyos retiros resultado en isomorfo gráficos. La gráfica construida de tal manera, había 96 nodos y 293 bordes.

Sin cambiar la idea de su construcción, varios trucos permiten una mejora en una gráfica con la misma propiedad con 24 nodos y 47 bordes.

Los trucos son:

1. En lugar de conectar los nodos $i$ a los nodos $v_{ec}$ siempre $i$ es de $e$, ello siempre que $i$ es de $e$ e $c$ es en cierto conjunto de vértices estable en el isomorfismo de subdiagramas.

2. En lugar de reemplazar todos los bordes con una copia de $G$ o $G'$, esto sólo lo suficiente de las aristas en el grafo completo para contener las dos especiales de bordes y ser estable en el isomorfismo de subdiagramas.

Es decir, comenzar con el gráfico descrito por el cartel original:

Reemplace el verde sólido bordes con una copia de $G$ como sigue:

Reemplace el punteada de color verde borde con una copia de $G$ sin uno de sus especiales de bordes:

El resultado final es la prometida.

No es difícil ver a partir de las 1-valente vértices que este gráfico no tiene automorfismos.

Answer 2

No es una respuesta, solo un comentario extendido.

Para$n \leq 10$, dicho gráfico no existe.

Actualmente estoy comprobando$n = 11.$ ¿Hay alguna propiedad estructural que tenga un gráfico así, aparte de que esté conectado y no (en particular) transitivo de borde?

El siguiente es un programa simplificado de Sage utilizado para la comprobación en caso de que alguien quiera jugar con él.

 def edgeOrbits(G):
    # Gap expects us to send a permutation group acting on 1,...,n 
    G.relabel({i:i+1 for i in G})
    A,o = G.automorphism_group(order=True)
    if o == 1: return G.edges(labels=false)
    E = str([ [x,y] for x,y in G.edges(labels=false)])


    G.relabel({i:i-1 for i in G})
    return [(int(x)-1,int(y)-1) for x,y in gap("List(Orbits("+str(A._gap_())+"," + str(E) + ",OnSets), x->x[1]);")]


# Returns edges x,y,z so that G-x,G-y,G-z are isomorphic 
# yet the edges x,y,z are not mapped by an aumorphism of G, 
# or false if G has no such edges.    
def isNice(G):
    cann = {}
    for e in edgeOrbits(G):
        G.delete_edge(e)
        s = G.canonical_label().graph6_string()
        G.add_edge(e)
        if s not in cann:
            cann[s] = [e]
        else:
            cann[s] += [e]
            if len(cann[s]) >= 3:
                return cann[s]

    return false

# Find a graph with the stated property    
def findGraph(n):
    for G in graphs.nauty_geng(str(n) + " -c"):
        t = isNice(G)
        if t:
            print G.graph6_string(),t