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 siguiente gráfico de la izquierda 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 de algún otro grado y 1 vértice de tercer grado. La secuencia de grados del gráfico bipartitoabajo en el medio está (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 gráfico de la derecha abajo es (3 , 3, 3, 3, 3, 3, 2) y su partición de frecuencia es 7 = 6 + 1.
En general, hay muchos gráficos no isomorfos con una partición de frecuencia dada. Un gráfico y su complemento tienen la misma partición de frecuencia. Para cualquier partición p = f 1 + f 2 + ... + f k de un entero p > 1, que no sea p = 1 + 1 + 1 + ... + 1, hay al menos un gráfico simple (conectado) teniendo esta partición como su partición de frecuencia. [1]
Las particiones de frecuencia de varias familias de gráficos están completamente identificadas; no se identifican las particiones de frecuencia de muchas familias de grafos.
Para una partición de frecuencia p = f 1 + f 2 + ... + f k de un entero p > 1, su secuencia gráfica de grados se denota como ((d 1 ) f 1 ,(d 2 ) f 2 , (d 3 ) f 3 , ..., (d k ) f k ) donde los grados d i son diferentes y f i ≥ f j para i < j . Bhat Nayaket al. (1979) mostró que una partición de p con k partes, k ≤ parte integral de es una partición de frecuencia [2] de un grafo euleriano y viceversa.
Las particiones de frecuencia de familias de grafos como árboles , [3] grafos hamiltonianos [4] grafos dirigidos y torneos [5] e hipergrafos k-uniformes . [6] se han caracterizado.