Referencia para una clase de gráficos que conservan distancias de subgrafo cuando se ordenan

12

Digamos que un gráfico tiene la propiedad si sus vértices se pueden ordenar de tal manera que el gráfico inducido por los vértices tiene $G$ $M$ $v_1, v_2, \ldots v_n$ $H_i$ $\{v_1, \ldots, v_i\}$ para todo . En otras palabras, agregar el siguiente vértice en nuestro orden no afecta la distancia métrica del gráfico actual. $dist_{H_i} (v_j, v_k) = dist_G(v_j, v_k)$ $j,k \leq i$

Un ejemplo de tal gráfico es la cuadrícula regular . $n \times n$

¿Esta propiedad o clase de gráficos tiene un nombre? ¿Han sido estudiados?

reference-request graph-theory mich
fuente

Un ejemplo simple de un gráfico que no no tiene esta propiedad es la

-ciclo para

. Esto se debe a que, para cualquier orden, las subgrafías

deben estar conectadas, por lo que en el momento

,

es una línea de longitud

, por lo que algunos vértices son distancia

aparte.

k

$k$

k \geq 5

$k \ge 5$

H_{i}

$H_i$

i = ⌊ k / 2 ⌋ + 2 < k

$i = \lfloor k/2 \rfloor +2 < k$

H_{i}

$H_i$

i - 1

$i-1$

i - 1 > ⌊ k / 2 ⌋

$i-1 > \lfloor k/2 \rfloor$

Andrew Morgan

Por otro lado, un candidato natural para encontrar un buen orden

es hacer un BFS a partir de una elección arbitraria de

. Al ver

como el árbol BFS con algunos bordes adicionales, parece que el único obstáculo para tener la propiedad

es para que haya algo "como" un

-ciclo para

en

. Por "me gusta" quiero decir que hay un ciclo

v_{1}, \dots, v_{n}

$v_1, \ldots, v_n$

v_{1}

$v_1$

G

$G$

M

$M$

k

$k$

k \geq 5

$k \ge 5$

G

$G$

k

$k$

con

para que

en

. Si llamamos a este ciclo "mínimo", ¿es cierto que la propiedad

es equivalente a la inexistencia de ciclos mínimos de longitud de al menos 5?

v_{1}, \dots, v_{k}, v_{k + 1} = v_{1}

$v_1, \ldots, v_k, v_{k+1}=v_1$

k \geq 5

$k \ge 5$

d (v_{i}, v_{j}) = | i - j |

$d(v_i,v_j) = |i-j|$

G

$G$

M

$M$

Andrew Morgan

1

Un cubo tiene un ciclo inducido e isométrico de 6 (eliminar dos vértices opuestos del cubo; lo que queda es el ciclo 6), pero se puede ordenar de forma que conserve la distancia (por ejemplo, BFS). Entonces tus

-cycles no siempre son obstáculos. Este ejemplo también muestra que eliminar vértices con avidez que preservan las distancias puede atascarse, incluso cuando funciona algún otro orden.

k

$k$

David Eppstein

8

Parece que está preguntando acerca de los gráficos que admiten un orden de eliminación de preservación de la distancia que forma una clase de gráficos estudiados en este documento:

http://epubs.siam.org/doi/abs/10.1137/S0895480195291230?journalCode=sjdmec

JimN
fuente

2

También disponible gratuitamente en la página web del autor: lif-sud.univ-mrs.fr/%7Echepoi/dpo.ps

Florent Foucaud

8

No tengo una respuesta para toda la clase de gráficos, pero tres subclases de gráficos que tienen esta propiedad son los grafos distancia-hereditaria , gráficos de cuerdas , y grafo mediano .

$v_1$

Los gráficos cordales son los gráficos que tienen un orden con la propiedad de que cada vértice sucesivo, cuando se agrega, tiene una camarilla para sus vecinos. Este orden es obviamente preservar la distancia.

Del mismo modo, los gráficos medianos (incluido su ejemplo de cuadrícula) tienen la propiedad de que, para cualquier orden de amplitud, cada vértice tiene un vecindario de hipercubo en el momento en que se agrega. (Ver páginas 76–77 de Eppstein et al, "Media Theory", Springer, 2008). Nuevamente, esta propiedad significa que la suma no puede cambiar las distancias entre los vértices anteriores.

Hay una clase de gráficos para los que no conozco un nombre, que generalicen tanto los gráficos cordales como los gráficos de distancia, que pueden reconocerse en el tiempo polinómico y que tienen su propiedad. Son los gráficos conectados que se pueden construir a partir de un único vértice agregando vértices uno por uno, donde los vecinos de cada nuevo vértice son un subconjunto de uno de los barrios cerrados del gráfico anterior. Son casi (pero no del todo) lo mismo que los gráficos desmontables, la diferencia es que el nuevo vértice no tiene que ser adyacente al vértice cuyo vecindario se está copiando. Un orden de eliminación de un gráfico cordal es una construcción de este tipo donde cada nuevo vértice elige un subconjunto de camarillas de un vecindario. Del mismo modo, los gráficos hereditarios de distancia tienen una construcción de este tipo donde los vecinos de cada nuevo vértice son un vecindario cerrado completo, un vecindario abierto o un vértice único. Cada nuevo vértice no puede cambiar las distancias de los vértices anteriores, por lo que esta secuencia de construcción tiene la propiedad que está buscando.

Si define un vértice v como "removible" si pudiera ser el último en esta secuencia (tiene un vecindario abierto que es un subconjunto del vecindario cerrado de otra persona), entonces eliminar otros vértices removibles no cambia la remoción de v : si la vecindad de v es un subconjunto de u, y eliminamos u por tener una vecindad que es un subconjunto de w, entonces v todavía es removible porque su vecindad sigue siendo un subconjunto de w. Por lo tanto, las secuencias de pasos de eliminación que podemos seguir para llevar un gráfico de vuelta a la nada forman un antimatroide, y una secuencia de este tipo se puede encontrar en tiempo polinómico mediante un algoritmo codicioso que elimina repetidamente un vértice removible siempre que puede encontrar uno. Invertir la salida de este algoritmo proporciona la secuencia de construcción para el gráfico dado. La gráfica del cubo da un ejemplo de una gráfica que tiene su propiedad (una gráfica mediana) pero no es construible de esta manera. Creo que los gráficos medios que se pueden construir de esta manera son exactamente los gráficos cuadrados (que incluyen las cuadrículas regulares). Los gráficos que tienen una secuencia de construcción de este tipo también incluyen todos los gráficos que tienen un vértice universal, como los gráficos de rueda , por lo que (a diferencia de los gráficos cordales y los gráficos de distancia hereditaria) no son perfectos y no están cerrados bajo subgrafos inducidos.

David Eppstein
fuente

La propiedad de esta clase de gráficos de la que no está seguro recuerda una orden de eliminación de dominación. Este artículo parece relevante para la pregunta original: epubs.siam.org/doi/abs/10.1137/…

JimN

Creo que el orden de eliminación de dominatlon puede ser lo mismo que la capacidad de desmontaje. Pero debe vincular ese documento en una respuesta real, porque su "orden de eliminación de preservación de la distancia" parece ser exactamente lo que está pidiendo la pregunta original.

David Eppstein

Referencia para una clase de gráficos que conservan distancias de subgrafo cuando se ordenan

Respuestas: