Characterization of the odd graphs Ok by parameters

✍ Scribed by Aeryung Moon

• Publisher: Elsevier Science
• Year: 1982
• Tongue: English
• Weight: 776 KB
• Volume: 42
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(82)90057-7

✦ Synopsis

In this note, we settle a problem of N. Biggs [4, p. 801 by showing that for each k, no distance regular graph non-isomorphic to the odd graph Ok can have the same parameters as Ok. A related charxterization of certain graphs associated with the Johnson scheme J(2& + 1, k) is also g&en. By a graph we shall mean a finite, undirected, simple graph. Let G be a graph with vertex set V(G) and edge set E(G). For any two vertices U, o in the same connected component of G, the distance d(u, U) between u and u is the length of a shortest path joining u and o. Then d(u, u) = 0 for all u, and d(u, U) = 1 if and only if u, 1) are adjacent, denoted u -v. If u E V(G), we set Q(U) ={u E V(G): d(u, v) = i} and n,(u) = (D,(u)l. If h(u) is constant for all u, then we just write it as P+. If u, u E V(G) with d( u, u) = i, then we let P;(u, u,=I{w E V(G): d(u, w) =j, d(u, w)= k}l.