¿Existe alguna forma de añadir un nodo a un dígrafo sin añadir una nueva ordenación topológica?

Question

Tengo un dígrafo con $n$ nodos. Quiero añadir un nuevo nodo al grafo, pero no necesariamente quiero añadir una nueva arista para conectar este nodo. En esencia, quiero que el grafo siga siendo acíclico.

¿Puedo añadir este nuevo nodo sin cambiar el número de tipos topológicos en el gráfico?

Supongamos que acabo añadiendo nuevas aristas para conectar el nuevo nodo. ¿Puedo hacerlo y el resultado en un gráfico que tiene $a(n + 1)$ tipos topológicos, con $a$ que representa el número de ordenaciones topológicas antes de la adición?

Answer 1

Si añades un nuevo vértice $v$ a un grafo y añadir aristas $xv$ para cada vértice $x$ en el gráfico, el $v$ debe llegar al final de cualquier ordenación topológica del nuevo grafo, por lo que habrá el mismo número de ordenaciones topológicas que si $v$ no se añadieron.

Sospecho que su otra pregunta, preguntando si se puede añadir $v$ de tal manera que el número de tipos topológicos se multiplique por un factor de $n+1$ es mucho más difícil. Dudo que todos los grafos tengan esta propiedad, y no tengo ni idea de cómo clasificar los que la tienen, pero puedo imaginar que existe un algoritmo inteligente que puede buscar metódicamente esa forma de añadir un nuevo vértice.