Johnson graph
Encyclopedia
{infobox graph
| name = Johnson graph
| namesake = Selmer M. Johnson
| vertices =
| edges =
| diameter =
| properties = (
Johnson graphs are a special class of graphs
used in several branches of mathematics
and computer science
. The vertices are the -element subsets of an -element set. Two vertices are adjacent when they meet in a -element set. Johnson graphs, denoted by , are closely related to the Johnson scheme, both of which are named after Selmer M. Johnson
.
is the octahedral graph
| name = Johnson graph
| namesake = Selmer M. Johnson
Selmer M. Johnson
Selmer Martin Johnson was an American mathematician, a researcher at the RAND Corporation.-Biography:Johnson was born on May 21, 1916 in Buhl, Minnesota. He earned a B.A. and then an M.A. in mathematics from the University of Minnesota in 1938 and 1940 respectively...
| vertices =
| edges =
| diameter =
| properties = (
Johnson graphs are a special class of graphs
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
used in several branches of mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
. The vertices are the -element subsets of an -element set. Two vertices are adjacent when they meet in a -element set. Johnson graphs, denoted by , are closely related to the Johnson scheme, both of which are named after Selmer M. Johnson
Selmer M. Johnson
Selmer Martin Johnson was an American mathematician, a researcher at the RAND Corporation.-Biography:Johnson was born on May 21, 1916 in Buhl, Minnesota. He earned a B.A. and then an M.A. in mathematics from the University of Minnesota in 1938 and 1940 respectively...
.
Special Cases
is the complete graphComplete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
is the octahedral graph