Gráficos con sólo discontinuo perfecto matchings

Question

Deje $G(V,E)$ un gráfico. Estoy en busca de gráficos con sólo discontinuo perfecto elecciones (es decir, cada borde sólo aparece en la mayoría de los una de las perfectas elecciones).

Ejemplos:

• Cíclico gráfico de $C_n$ incluso $n$, con $m=2$ discontinuo perfecto elecciones.
• Grafo completo $K_4$, con $m=3$ discontinuo perfecto elecciones.

Tengo tres preguntas:

1. Cómo son los gráficos de este tipo se llama?
2. Hay otros ejemplos de $C_n$ e $K_4$?
3. ¿Cuál es el máximo número de $m$ de perfecto elecciones, si la gráfica tiene sólo completamente distinto, perfecto elecciones?

Para la pregunta 3, a mí me parece que $K_4$ con $m=3$ diferente, distinto, perfecto matchings es la óptima, pero no tengo ninguna prueba de eso.

Cada sugerencia a una respuesta o a la literatura relevante sería muy apreciada!

Edit: estoy interesado en el grafo gráficos sólo por el momento.

Edit2: La respuesta a esta pregunta la he usado en un reciente artículo en physical Review Letters, donde puedo citar este MO pregunta como referencia [24]. Consulte la Figura 2 para obtener una variante de la aplicación de Ilya la respuesta. Gracias Ilya!

Answer 1

$m=3$ es de hecho el máximo, y $K_4$ es el único ejemplo de este valor de $m$.

Dos perfectas matchings formar un discontinuo de la unión de los ciclos. Si hay más de un ciclo, entonces usted puede cambiar uno de ellos, la obtención de una tercera coincidencia en los mismos bordes. Así que dos de las $m$ matchings forma un ciclo Hamiltoniano.

Suponga que $m\geq3$; considerar un ciclo Hamiltoniano $v_1,\dots,v_{2n}$ formado por las dos primeras elecciones, y comprobar cómo la tercera que parece.

Si algunos de sus edge $(v_i,v_j)$ subtienda un arco de longitud impar (es decir, si $i-j$ es impar), entonces podemos dividir los vértices fuera de este arco en parejas, y dividir el ciclo de $v_i,\dots,v_j$ en los bordes incluidos $(v_i,v_j)$, la obtención de una coincidencia de la intersección de la tercera, pero no coincide con él. Esto no debería ser posible; así cada arco subtendido es aún.

Ahora tome un borde $(v_i,v_j)$ subtiende un mínimo de dicho arco, y considerar una ventaja $(v_{i+1},v_k)$ de la tercera coincidencia (va otside este arco). Ahora dividir el ciclo de $v_i,v_j,v_{j+1},\dots,v_k,v_{i+1}$ en los bordes que contienen $(v_i,v_j)$, y dividir el resto de vértices en los bordes de la Hamiltoniana del ciclo (es posible, de acuerdo a la paridad). Si $2n>4$, de nuevo llegar a un cuarto de coincidencia de compartir los bordes con el tercero bot diferentes de ella.

Por lo tanto $2n\leq 4$ e $m\leq 3$.

Answer 2

Parece que Ilya Bogdanov ha contestado a su pregunta, pero aquí es un puntero a la literatura relacionada con la.

Un borde que aparece en más de un perfecto maridaje que se conoce como un obligando a borde. Che y Chen ha escrito una encuesta de la literatura de forzar a los bordes y temas relacionados.