Johnson-graaf

De Johnson-graaf J(5,2).

De complementgraaf van J(5,2)

Een Johnson-graaf $J(n,k)$ is een ongerichte graaf met als knopen alle deelverzamelingen met $k$ elementen uit een verzameling van $n$ elementen. Twee knopen zijn door een kant verbonden als en alleen als hun corresponderende deelverzamelingen exact $k-1$ gemeenschappelijke elementen hebben.

Johnson-grafen zijn genoemd naar de Amerikaanse wiskundige Selmer M. Johnson. Ze staan in verband met de zogenaamde Johnson-schema's, een klasse van associatieschema's in de algebraïsche combinatoriek. Ze hebben een hoge mate van symmetrie.

Voorbeelden

• $J(n,1)$ is isomorf met de volledige graaf $K_n$
• $J(n,0)$ is een triviale graaf bestaande uit een enkele knoop, corresponderend met de lege verzameling.
• $J(n,n)$ is een triviale graaf bestaande uit een enkele knoop, corresponderend met de volledige verzameling van $n$ elementen.
• $J(5,2)$ is de complementgraaf van de Petersen-graaf. Algemeen geldt dat $J(n,2)$ de complementgraaf is van de Kneser-graaf $K(n,2)$.

Merk op dat $J(n,k)$ en $J(n,n-k)$ isomorf zijn. De ene graaf kan uit de andere afgeleid worden door elke deelverzameling van $k$ elementen af te beelden op haar complement.

Eigenschappen

De Johnson-graaf $J(n,k)$ heeft $(\genfrac{}{}{0ex}{}{n}{k})$ knopen en $\frac{k(n-k)}{2}(\genfrac{}{}{0ex}{}{n}{k})$ kanten.

Johnson-grafen zijn reguliere grafen; alle knopen hebben dezelfde graad. Ze zijn bovendien afstandsregulier.

De afstand tussen twee knopen (dit is 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 $J(5,2)$ tussen de twee deelverzamelingen gelijk is aan 2.

Brian Alspach bewees in 2013 dat elke Johnson-graaf $J(n,k)$ Hamilton-verbonden is voor alle $n>1$. Dit betekent dat er een Hamiltonpad bestaat tussen elk paar knopen.

Verband met Johnson-schema

De Johnson-graaf $J(n,k)$ is nauw verwant met het Johnson-schema met $k$ klassen, dat ook wordt aangeduid als $J(n,k)$. Dit is een associatieschema gedefinieerd op de deelverzamelingen met $k$ elementen van een verzameling met $n$ elementen.

Twee deelverzamelingen behoren tot relatie $R_i$ (of zijn geassocieerd met het getal $i$) indien ze exact $k-i$ elementen gemeenschappelijk hebben. De Johnson-graaf is de voorstelling van de relatie $R_1$.