Partición de frecuencia de un gráfico

En la teoría de grafos , una disciplina dentro de las matemáticas , la partición de frecuencia de un grafo ( grafo simple ) es una partición de sus vértices agrupados por su grado. Por ejemplo, la secuencia de grados del grafo de la izquierda a continuación es (3, 3, 3, 2, 2, 1) y su partición de frecuencia es 6 = 3 + 2 + 1. Esto indica que tiene 3 vértices con algún grado, 2 vértices con algún otro grado y 1 vértice con un tercer grado. La secuencia de grados del grafo bipartito en el medio a continuación es (3, 2, 2, 2, 2, 2, 1, 1, 1) y su partición de frecuencia es 9 = 5 + 3 + 1. La secuencia de grados del grafo de la derecha a continuación es (3, 3, 3, 3, 3, 3, 2) y su partición de frecuencia es 7 = 6 + 1.

• 
  Un gráfico con partición de frecuencia 6 = 3 + 2 + 1.
• 
  Un grafo bipartito con partición de frecuencia 9 = 5 + 3 + 1.
• 
  Un gráfico con partición de frecuencia 7 = 6 + 1.

En general, existen muchos grafos no isomorfos con una partición de frecuencia dada. Un grafo y su complemento tienen la misma partición de frecuencia. Para cualquier partición p = f ₁ + f ₂ + ... + f _k de un entero p > 1, distinto de p = 1 + 1 + 1 + ... + 1, existe al menos un grafo simple (conexo) que tiene esta partición como su partición de frecuencia. ^{[ 1 ]}

Se identifican completamente las particiones de frecuencia de varias familias de grafos; sin embargo, no se identifican las particiones de frecuencia de muchas familias de grafos.

Para una partición de frecuencia p = f ₁ + f ₂ + ... + f _k de un entero p > 1, su secuencia de grados gráficos se denota como ((d ₁ ) ^{f ₁} ,(d ₂ ) ^{f ₂} , (d ₃ ) ^{f ₃} , ..., (d _k ) ^{f _k} ) donde los grados d _i son diferentes y f _i ≥ f _j para i  < j . Bhat-Nayak et al. (1979) demostraron que una partición de p con k partes, k ≤ parte entera de ${\displaystyle (p-1)/2}$es una partición de frecuencia ^{[ 2 ]} de un grafo euleriano y viceversa.

Se han caracterizado las particiones de frecuencia de familias de grafos como árboles , ^{[ 3 ]} grafos hamiltonianos ^{, [ 4 ]} grafos dirigidos y torneos , ^{[ 5 ]} y a hipergrafos k-uniformes . ^{[ 6 ]}

Aún no se han caracterizado las particiones de frecuencia de las siguientes familias de grafos:

• Gráficos de líneas
• Grafos bipartitos ^{[ 7 ]}

• Berge, C. (1989), Hipergrafos, Combinatoria de conjuntos finitos , Ámsterdam: North-Holland, ISBN 0-444-87489-5