Gráfico M 22

El grafo M ₂₂ , también llamado grafo de Mesner o grafo de Witt , ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]} es el único grafo fuertemente regular con parámetros (77, 16, 0, 4). ^{[ 5 ]} Se construye a partir del sistema de Steiner (3, 6, 22) representando sus 77 bloques como vértices y uniendo dos vértices si y solo si no tienen términos en común, o eliminando un vértice y sus vecinos del grafo de Higman-Sims . ^{[ 6 ] [ 7 ]}

Para cualquier término, la familia de bloques que lo contienen forma un conjunto independiente en este grafo, con 21 vértices. En un resultado análogo al teorema de Erdős-Ko-Rado (que puede formularse en términos de conjuntos independientes en grafos de Kneser ), estos son los conjuntos independientes máximos únicos en este grafo. ^{[ 4 ]}

Es uno de los siete grafos fuertes regulares sin triángulos conocidos . ^{[ 8 ]} Su espectro de grafos es (−6) ²¹ 2 ⁵⁵ 16 ¹ , ^{[ 6 ]} y su grupo de automorfismos es el grupo de Mathieu M22 . ^{[ 5 ]}

• Gráfico de Cameron
• Gráfico de Higman-Sims
• Gráfico de Gewirtz

• Gráfico M ₂₂ en MathWorld