Las citas que muestran menores son menores topológicos para gráficos subcúbicos

12

Si es un gráfico con el máximo grado 3 y es un menor de H , entonces es un menor topológica de .GHHGH

Wikipedia cita este resultado de la "teoría de grafos" de Diestel. Está listado como la Proposición 1.7.4 en la última versión del libro. El libro carece de prueba o cita.

¿Se conoce el paradero como prueba (original) de esto?

Además, ¿hay alguna referencia que demuestre que si es un camino o una subdivisión de una garra y es menor de entonces es un subgrafo de ? Se menciona aquí brevemente pero carece de referencia.H G HGHGH

reference-request graph-theory co.combinatorics graph-minor Eli
fuente
El libro está disponible en diestel-graph-theory.com
Alexander Langer
Gracias alexander Esa versión del libro no proporciona ninguna referencia o prueba de la propuesta, ¿sabe si la edición completa lo tiene u otra fuente?
Eli
2
Recuerdo haber buscado una cita para el segundo hecho que usted dijo, pero no encontré nada. La mejor cita que conozco para la primera declaración es el libro de Diestel, que no prueba la declaración. Esperaré para ver si alguien encuentra una cita. Si no, publicaré una prueba como respuesta.
Robin Kothari
1
@Robin, en este punto si publicas una prueba, eso es lo suficientemente bueno para mí. ¿Hay una manera apropiada de atribuirle si este resultado se usa en alguna parte? No estoy familiarizado con la política de intercambio de pila o la práctica estándar.
Eli
1
En realidad, la cita ya se ha discutido y resuelto aquí: meta.cstheory.stackexchange.com/questions/352/…
Aaron Sterling

Respuestas:

13

Si H G HG es un gráfico con el máximo grado 3 y es un menor de , entonces es un menor topológica de .HGH

Ya que es menor que H , G puede obtenerse de H eliminando bordes, vértices aislados y realizando contracciones de bordes. También es fácil demostrar que podemos insistir en que las operaciones del subgrafo se realicen primero, es decir, primero podemos realizar todas las eliminaciones de bordes y vértices y luego realizar todas las contracciones de bordes. Además, limitemos la definición de "contracción de borde" para no permitir bordes de contracción donde uno de los vértices tiene grado 1. Contratar dicho borde es lo mismo que eliminarlo, por lo que esto no cambiará la definición de gráficos menores.GHGH

Sea el gráfico obtenido de H al realizar primero todas las eliminaciones de borde / vértice. H ′H′HH′ todavía contiene como un menor. Si mostramos que H ' contiene G como un topológico menor, entonces hemos terminado, ya que la definición de topológico menor también permite la eliminación de bordes / vértices.GH′G

Desde GH′H′

H′G

H1H2H2H1H′GGH′H

GHGH

GHHHG

También necesitábamos este resultado para un trabajo una vez, por lo que incluimos una breve prueba en nuestro trabajo. Puede encontrar el resultado en la complejidad de la consulta cuántica de propiedades de gráficos cerrados menores . Se menciona en la página 13. Sin embargo, este hecho está oculto en la prueba de otra cosa y no se declara explícitamente como un teorema.

Lo que también es interesante es que hay un inverso a este teorema:

GGG

Robin Kothari
fuente
1
Gracias. Si te encuentras con una cita publicada para estos resultados, todavía me gustaría, pero esto es estelar.
Eli
Esta respuesta ahora aparece en el blog de la comunidad.
Aaron Sterling
Buena respuesta, pero creo que su técnica de rechazar las contracciones de grado 1 tiene un defecto. Por ejemplo, considere G = K_4 menos cualquier borde. La contratación a lo largo de los dos vértices de grado 3 en G producirá el gráfico de ruta P_3, con grado máximo 2. En cambio, si no permite ninguna contracción en un borde que sería equivalente a alguna eliminación, la prueba debería pasar. Formalmente, prohíbe cualquier contracción entre los vértices x e y si gamma (x) \ {y} = gamma (y) \ x. Se muestra fácilmente que cualquier contracción que no viole esta restricción dará como resultado un nuevo vértice de grado no disminuido.
RussellStewart
@ user2237635: Tienes razón, gracias.
Robin Kothari