En la teoría de grafos , hay dos propiedades relacionadas de un hipergráfico que se denominan "ancho". Dada una hipergrafía H = ( V , E ), decimos que un conjunto K de aristas fija otro conjunto F de aristas si cada arista en F se cruza con alguna arista en K . [1] Entonces:
El gráfico de disyunción de H , denotado D( H ), es un gráfico donde cada arista en H es un vértice en D( H ), y cada dos aristas disjuntas en H son adyacentes en D( H ). Los emparejamientos en H corresponden a las camarillas en D( H ). Meshulam [2] caracterizó los anchos de una hipergrafía H en términos de las propiedades de D( H ). Para cualquier entero positivo r :
El gráfico lineal de H , denotado L( H ), es un gráfico donde cada arista en H es un vértice en L( H ), y cada dos aristas que se cruzan en H son adyacentes en L( H ). Los emparejamientos en H corresponden a los conjuntos independientes en L( H ). Dado que L( H ) es el complemento de D( H ), la caracterización anterior se puede traducir a L( H ):
El número de dominación de un gráfico G , denotado γ ( G ), es el tamaño más pequeño de un conjunto de vértices que domina todos los vértices de G. El ancho de un hipergráfico es igual al número de dominación o su gráfico lineal: w( H ) = γ (L( H )). Esto se debe a que las aristas de E son los vértices de L( H ): cada subconjunto de E que fija E en H corresponde a un conjunto de vértices en L( H ) que domina todos los L( H ).
El número de dominación independiente de un grafo G , denotado iγ ( G ), es el máximo, sobre todos los conjuntos independientes A de G , del conjunto más pequeño que domina A. [4] El ancho coincidente de un hipergráfico es igual al número de dominación de la independencia o su gráfico lineal: mw( H ) = iγ (L( H )). Esto se debe a que cada M coincidente en H corresponde a un conjunto independiente I M en L( H ), y cada subconjunto de E que fija Men H corresponde a un conjunto que domina I M en L( H ).