24 votos

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

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:

Example of a graph on 6 nodes

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.

7voto

tessein Puntos 1705

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:

original graph

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

first edge replacement

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

second edge replacement

El resultado final es la prometida.

final graph

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

5voto

Roddy Puntos 32503

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
 

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X