thumb|280px|Johnson-graaf thumb|280px|Complementgraaf van
Een Johnson-graaf is een ongerichte graaf met als knopen alle deelverzamelingen met elementen uit een verzameling van elementen. Twee knopen zijn door een kant verbonden dan en slechts dan als hun corresponderende deelverzamelingen beide dezelfde elementen hebben. De grafen zijn naar de Amerikaanse wiskundige Selmer Johnson genoemd en hebben een hoge mate van symmetrie.
Voorbeelden is isomorf met de volledige graaf . is een triviale graaf die uit maar een enkele knoop bestaat, corresponderend met de volledige verzameling van elementen. is de graaf die met het regelmatige achtvlak overeenkomt. is de complementgraaf van de Petersengraaf. Algemeen geldt dat de complementgraaf is van de Kneser-graaf . is de graaf die met het regelmatige twaalfvlak overeenkomt.
Merk op dat en isomorf zijn. De ene graaf kan uit de andere worden afgeleid door elke deelverzameling van elementen op het complement ervan af te beelden. Dat betekent dat bijvoorbeeld ook isomorf is met de volledige graaf .
Eigenschappen De Johnson-graaf heeft knopen en kanten.
Johnson-grafen zijn reguliere grafen, alle knopen hebben dezelfde graad.
De afstand tussen twee knopen, de lengte van het kortste pad ertussen, in een Johnson-graaf is gelijk aan de helft van de hammingafstand tussen hun corresponderende deelverzamelingen. Bijvoorbeeld de deelverzamelingen {1,2} en {3,4} van {1,2,3,4,5} kan men voorstellen door de woorden 11000 en 00110. De hammingafstand daartussen is 4, terwijl de afstand in de Johnson-graaf tussen de twee deelverzamelingen gelijk is aan 2.
Brian Alspach heeft in 2013 bewezen dat elke Johnson-graaf Hamilton-verbonden is voor alle .. Johnson graphs are Hamilton-connected, 1 juni 2012. in Ars mathematica contemporanea 2013, 6 , blz 21-23 Dit betekent dat er een hamiltonpad bestaat tussen elk paar knopen.
Categorie:Grafentheorie