M 22 graf
| M 22 graf, Mesner graf | |
|---|---|
 | |
| Döpt efter | Mathieu grupp M 22 , Dale M. Mesner |
| Vertices | 77 |
| Kanter | 616 |
| Tabell över grafer och parametrar | |
M . 22- grafen , även kallad Mesner-grafen eller Witt-grafen , är den unika starkt regelbundna grafen med parametrar (77, 16, 0, 4) Det är konstruerat från Steiner-systemet (3, 6, 22) genom att representera dess 77 block som hörn och sammanfoga två hörn om de inte har några termer gemensamma eller genom att ta bort en vertex och dess grannar från Higman-Sims-grafen .
För varje term bildar blockfamiljen som innehåller den termen en oberoende uppsättning i denna graf, med 21 hörn. I ett resultat som är analogt med Erdős–Ko–Rado-satsen (som kan formuleras i termer av oberoende mängder i Kneser-grafer ), är dessa de unika maximala oberoende mängderna i denna graf.
Det är en av sju kända triangelfria, starkt regelbundna grafer. Dess grafspektrum är (−6) 21 2 55 16 1 , och dess automorfismgrupp är Mathieu-gruppen M22 .