Gráficos en los que todos los caminos más cortos son únicos

22

Estoy buscando gráficos conectados, no ponderados y no direccionados , en los que para cada par , hay una ruta única que se da cuenta de la distancia .G=(V,E)u,vVuvd(u,v)

¿Es esta clase de gráficos bien conocida? ¿Qué otras propiedades tiene? Por ejemplo, cada árbol es de este tipo, así como cada gráfico sin un ciclo par. Sin embargo, hay gráficos que contienen ciclos pares que son de este tipo.

László Kozma
fuente

Respuestas:

25

De acuerdo con el Sistema de información sobre clases de gráficos y sus inclusiones, estos gráficos se estudian con el nombre de " gráficos geodésicos ".

Tsuyoshi Ito
fuente
10

Tales gráficos son de hecho geodésicos. Un gráfico es bigeodético, si hay como máximo dos caminos más cortos entre cualquier par de vértices. En general, un gráfico es -geodetic si hay como máximo rutas más cortas entre cualquier par de vértices.kk

Otro ejemplo de un gráfico geodésico es un gráfico de bloques. Un gráfico es un gráfico de bloques si se puede construir a partir de un árbol reemplazando cada borde con una camarilla. De manera equivalente, esto se conoce como un gráfico cordal sin diamantes. Un diamante es un menos un borde. Por ejemplo, vea el Teorema 1.1 en Le, Van Bang y Nguyen Ngoc Tuy. "El cuadrado de un gráfico de bloque". Matemáticas discretas 310.4 (2010): 734-741.K4

Juho
fuente