The Johnson graph J(d, r) is unique if (d, r) ≠ (2, 8)

✍ Scribed by Paul Terwilliger

• Book ID: 103056685
• Publisher: Elsevier Science
• Year: 1986
• Tongue: English
• Weight: 740 KB
• Volume: 58
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(86)90160-3

✦ Synopsis

We use the classical Root Systems to show the Johnson graph J (d, r) (2 <~ 2d ~ r < oo) is the unique distance-regular graph with its intersection numbers when (d, r):~ (2, 8). Since this exceptional case has been dealt with by Chang [6] this completes the characterization problem for the Johnson graph.

We note (see Biggs ) that for any distance-regular graph all intersection numbers are determined from q, ai, and bi (0 ~< i ~< d).

Many authors have asked whether J(d, r) is the unique distance-regular graph with its own intersection numbers, and there are some partial results.

The uniqueness of J(2, r) was proved by Shrikhande [19] for r < 6, Hoffman [101 and Chang [6] for r = 7, and Conner [7] for r > 8. Chang showed there were exactly 4 nonisomorphic graphs with the intersection numbers of J(2, 8). The graph J(3, r) was shown to be unique by Aigner [1] for r <~ 8, Moon [14] for r =