Es posible que simplemente no han pensado duro lo suficiente acerca de esto, pero he estado trabajando en esto por un día o dos y no llegar a ninguna parte.
Usted puede definir la noción de "cubrir gráfico" en la teoría de grafos, de forma análoga a la cobertura de los espacios. (En realidad creo que hay algún sentido-tal vez en topología diferencial, en el que las nociones de acuerdo exactamente, pero esa no es la cuestión.) De todos modos, se comporta como una cubierta del espacio de los ascensores de rutas y así sucesivamente.
También hay una "cobertura universal", que creo que cumple la misma característica universal como topológica universal cubre, pero no estoy seguro. Universal cubre son acíclicos (simplemente conectado) en la teoría de grafos, así que son los árboles, generalmente infinito. La universalización de la cobertura no determina la gráfica; por ejemplo, cualquiera de los dos k-regular gráficos (k > 1) tienen la misma cobertura universal. Usted puede construir un montón de otros pares, también.
Estoy interesado en las condiciones necesarias y suficientes para los dos gráficos $G, H$ a tener la misma cobertura universal. Una de tales condiciones (estoy bastante seguro!) es si se puede dar una correspondencia 1-1 entre los senderos en $G$ y senderos en $H$ que conserva grado de secuencias. Desafortunadamente, esto no me ayuda mucho, ya que este es básicamente un infinito condición. Hay algunos menos evidente pero más fácilmente seleccionable condición? En particular, es posible determinar si dos (finito) gráficos tienen la misma cobertura universal en el polinomio de tiempo?
