en>ChrisGualtieri: General fixes / CHECKWIKI fixes using AWB

2012-08-31T01:31:52Z

General fixes / CHECKWIKI fixes using AWB

New page

{{infobox graph
| name = Johnson graph
| image = [[File:Johnson graph 5,2.svg|280px]]
| image_caption = The Johnson graph ''J''(5,2)
| namesake = [[Selmer M. Johnson]]
| vertices = <math>\binom{n}{k}</math>
| edges = <math>\frac{k (n - k)}{2} \binom{n}{k}</math>
| diameter = <math>\min(k,n-k)</math>
| properties = [[Regular graph|<math>(k(n-k))</math>-regular]] [[Vertex-transitive graph|Vertex-transitive]] [[Distance-transitive graph|Distance-transitive]]
| notation = <math>J(n,k)</math>
}}
'''Johnson graphs''' are a special class of [[undirected graph]]s defined from systems of sets. The vertices of the Johnson graph <math>J(n,k)</math> are the <math>k</math>-element subsets of an <math>n</math>-element set; two vertices are adjacent when they meet in a <math>(k-1)</math>-element set.<ref name="hs93">{{citation
| last1 = Holton | first1 = D. A.
| last2 = Sheehan | first2 = J.
| contribution = The Johnson graphs and even graphs
| doi = 10.1017/CBO9780511662058
| isbn = 0-521-43594-3
| location = Cambridge
| mr = 1232658
| page = 300
| publisher = Cambridge University Press
| series = Australian Mathematical Society Lecture Series
| title = The Petersen graph
| url = http://books.google.com/books?id=sMSOSgbCx3kC&pg=PA300
| volume = 7
| year = 1993}}.</ref> Both Johnson graphs and the closely related [[Johnson scheme]] are named after [[Selmer M. Johnson]].

==Special Cases==
*<math>J(n,1)</math> is the [[complete graph]] {{math|''K''''n''}}.
*<math>J(4,2)</math> is the [[octahedral graph]].
*<math>J(5,2)</math> is the [[complement graph]] of the [[Petersen graph]],<ref name="hs93"/> hence the [[line graph]] of {{math|''K''''5''}}. More generally, for all {{mvar|n}}, the Johnson graph <math>J(n,2)</math> is the complement of the [[Kneser graph]] <math>KG(n,2)</math>

==Properties==
In the Johnson graph, the distance between every two vertices is half of the [[Hamming distance]] between the sets corresponding to the vertices. Johnson graphs are [[distance-transitive graph]]s: there is a [[graph automorphism]] mapping any pair of vertices to any other pair at the same distance.<ref name="c99">{{citation
| last = Cameron | first = Peter J.
| isbn = 9780521653787
| page = 95
| publisher = Cambridge University Press
| series = London Mathematical Society Student Texts
| title = Permutation Groups
| url = http://books.google.com/books?id=4bNj8K1omGAC&pg=PA95
| volume = 45
| year = 1999}}.</ref>

As a consequence of being distance-transitive, every Johnson graph is also [[distance-regular graph|distance-regular]]. This means that, for every possible distance <math>d</math> between two vertices in the graph, there is a triple of numbers <math>(a_d,b_d,c_d)</math> such that, for every pair <math>(v,w)</math> of vertices at distance <math>d</math> from each other, <math>w</math> has exactly <math>a_i</math> neighbors at distance <math>d</math> from <math>v</math>, exactly <math>b_i</math> neighbors at distance <math>d+1</math> from <math>v</math>, and exactly <math>c_i</math> neighbors at distance <math>d-1</math> from <math>v</math>. These triples of numbers can be grouped into a [[matrix (mathematics)|matrix]] with one column per distance, called the intersection array of the graph, and this intersection array may be used to classify the distance-transitive graphs. It turns out that the intersection arrays of Johnson graphs are almost always enough to classify them completely: except for <math>J(8,2)</math>, each Johnson graph has an intersection array that is not shared with any other graph. However, the intersection array of <math>J(8,2)</math> is shared with three other distance-regular graphs that are not Johnson graphs.<ref name="hs93"/>

Every Johnson graph is Hamilton-connected, meaning that every pair of vertices forms the endpoints of a [[Hamiltonian path]] in the graph. In particular this means that it has a Hamiltonian cycle.<ref>{{citation
| last = Alspach | first = Brian
| issue = 1
| journal = Ars Mathematica Contemporanea
| pages = 21–23
| title = Johnson graphs are Hamilton-connected
| url = http://amc.imfm.si/index.php/amc/article/view/291
| volume = 6
| year = 2013}}.</ref>

==Relation to Johnson scheme==
The Johnson graph <math>J(n,k)</math> is closely related to the [[Johnson scheme]], an [[association scheme]] in which each pair of {{mvar|k}}-element sets is associated with a number, half the size of the [[symmetric difference]] of the two sets.<ref name="c99"/> The Johnson graph has an edge for every pair of sets at distance one in the association scheme, and the distances in the association scheme are exactly the [[shortest path]] distances in the Johnson graph.<ref>The explicit identification of graphs with association schemes, in this way, can be seen in {{citation
| last = Bose | first = R. C.
| journal = Pacific Journal of Mathematics
| mr = 0157909
| pages = 389–419
| title = Strongly regular graphs, partial geometries and partially balanced designs
| volume = 13
| year = 1963}}.</ref>

The Johnson scheme is also related to another family of distance-transitive graphs, the [[odd graph]]s, whose vertices are <math>k</math>-element subsets of an <math>(2k+1)</math>-element set and whose edges correspond to disjoint pairs of subsets.<ref name="c99"/>

==References==
{{reflist}}

==External links==
*{{mathworld|title=Johnson Graph|urlname=JohnsonGraph}}
*{{cite web
| url = http://www.win.tue.nl/~aeb/graphs/Johnson.html
| title = Johnson graphs
| first = Andries E.
| last = Brouwer
| authorlink = Andries E. Brouwer
}}

[[Category:Parametric families of graphs]]
[[Category:Regular graphs]]

Saturated measure - Revision history

en>ChrisGualtieri: General fixes / CHECKWIKI fixes using AWB