¿Puede el Grafo Completo de diez vértices ser cubierto por aristas por tres copias del Grafo de Petersen?

Question

Otra forma de verlo ... Colorea los bordes del grafo completo con 3 colores, de manera que tres subgrafos sean cada uno una copia del Grafo de Petersen. Escuché en algún lugar que se puede hacer (¡Quizás no debería seguir en MathOverflow!) pero pasé todo el fin de semana intentándolo y me he convencido de que es imposible. Gracias de antemano por tus comentarios.

Answer 1

La sección 1.5.1 en Espectros de grafos por Brouwer y Haemers dice que no existe tal descomposición. (PDF descargable aquí)

No voy a pretender entender la demostración, pero está justo al principio del libro, así que tal vez sea posible leer solo un poco y entender qué está pasando.

Encontré este resultado citado en un par de lugares como una sorprendente aplicación del álgebra lineal a la teoría de grafos.

Addendum: Aquí hay otra descripción, posiblemente más legible, de la misma técnica. (PDF)

Addendum: Sin embargo, esta página dice que puedes particionar un doble $K_{10}$ en seis grafos de Petersen!

Answer 2

También se proporciona una prueba de imposibilidad en Treinta y tres miniaturas: Aplicaciones matemáticas y algorítmicas del álgebra lineal, específicamente en la Miniatura 13, "Tres Petersen no son suficientes". Pude ver una parte sustancial de esto como resultado de Google Books.

Answer 3

Esto se puede verificar computacionalmente. Aquí está mi código de GAP:

F:=[[1,2],[2,3],[3,4],[4,5],[1,5],[6,8],[8,10],[7,10],[7,9],[6,9],[1,6],[2,7],[3,8],[4,9],[5,10]];

En lo anterior, F es el conjunto de aristas del grafo de Petersen.

count:=0;
S:=[];
for alpha in SymmetricGroup(10) do
  F2:=OnSetsSets(F,alpha);
  count:=count+1;
  if(Intersection(F,F2)=[]) then
    S:=Concatenation(S,[F2]);
    Print(Size(S)," de ",count," de ",Factorial(10),"; esperando: ",1.0*Factorial(10)*Size(S)/count,"\n");
  fi;
od;

Lo anterior genera una lista S de grafos isomorfos al grafo de Petersen F que no comparten una arista.

B:=[S[1],S[1]];
best:=Size(Intersection(B[1],B[2]));
for i in [1..Size(S)] do
  for j in [i+1..Size(S)] do
    F1:=S[i];
    F2:=S[j];
    int:=Size(Intersection(F1,F2));
    if(int

``

Lo anterior intenta encontrar dos miembros de S, denominados F1 y F2, que son disjuntos en aristas. No encuentra ninguno. Lo mejor que encuentra es lo siguiente:

Aquí los dos últimos grafos comparten las 6 aristas resaltadas en negrita.

``