×

zbMATH — the first resource for mathematics

Root systems and the Johnson and Hamming graphs. (English) Zbl 0614.05048
Let \(\Gamma\) be any distance regular graph with diameter d, \(c_ 2\geq 0\) and \[ c_ i-c_{i-1}+b_{i-1}-b_ i-a_ i-2=0. \] Then it is shown that \(\Gamma\) is a graph of Hamming type one of the Johnson graphs, the halved graph of the n-cube, a cocktail party graph, the Shrikhande graph or one of a finite number of exceptional graphs with \(d\leq 8.\)
This result improves an earlier result of the author. The proof is built round the idea that any \(\Gamma\) satisfying the equation above can be represented by a set of equi-length vectors spanning a Euclidean space which also contains a root system consisting of an orthogonal union of root systems of type \(A_ n\), \(D_ n\), \(E_ 6\), \(E_ 7\), \(E_ 8\). The graphs listed above appear as consequences of the form of the root system.
Reviewer: D.A.Holton

MSC:
05C75 Structural characterization of families of graphs
05C99 Graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aigner, M., On the tetrahedral graph, Pacific J. math., 25, 219-228, (1968) · Zbl 0157.31402
[2] Bennai, E.; Ito, T., ()
[3] Biggs, N.L., Algebraic graph theory, (1974), Cambridge University Press Cambridge · Zbl 0501.05039
[4] Biggs, N.L., Automorphic graphs and the Krein condition, Geom. dedicata, 5, 117-127, (1976) · Zbl 0333.05108
[5] Bose, R.C.; Laskar, R., A characterization of tetrahedral graphs, J. combin. theory, 3, 366-385, (1967) · Zbl 0155.31902
[6] Cameron, P.J., There are only finitely many distance-transitive graphs of given valency greater than two, Combinatorica, 2, 9-13, (1982) · Zbl 0507.05037
[7] Cameron, P.J.; Goethals, J.M.; Seidel, J.J.; Shult, E., Line graphs, Root systems, and elliptic geometry, J. algebra, 43, 305-327, (1976) · Zbl 0337.05142
[8] Chang, L.C., The uniqueness and non-uniqueness of the triangular association schemes, Sci. record, math. new ser., 3, 604-613, (1959) · Zbl 0089.15102
[9] Cohen, A.M., A synopsis of known distance-regular graphs with large diameters, Mathematisch centrum ZW, 168/81, (1981) · Zbl 0483.05034
[10] Connor, W.S., The uniqueness of the triangular association scheme, Ann. math. statist., 29, 262-266, (1958) · Zbl 0085.35601
[11] Delsarte, Ph., An algebraic approach to the association schemes of coding theory, Phillips res. rep., Suppl. 10, (1973) · Zbl 1075.05606
[12] Dowling, T.A., A characterization of the T.-graph, J. combin. theory, 6, 251-263, (1969) · Zbl 0182.58003
[13] Egawa, Y., Characterization of H(n, Q) by the parameters, J. combin. theory, ser. A, 31, 108-125, (1981) · Zbl 0472.05056
[14] Hiller, H., Geometry of Coxeter groups, () · Zbl 0483.57002
[15] Hoffman, A.J., On the uniqueness of the triangular association scheme, Ann. math. statist., 31, 492-497, (1960) · Zbl 0091.31504
[16] Humphreys, J.E., Introduction to Lie algebras and representation theory, (1976), Springer-Verlag New York · Zbl 0254.17004
[17] Ivanov, A.A., A diameter bound for distance-regular graphs, Soviet math. dokl., 271, 789-792, (1983)
[18] Liebler, R.A., On the uniqueness of the tetrahedral association schemes, J. combin. theory, ser. B, 22, 246-262, (1977) · Zbl 0358.05011
[19] McPherson, H.D., Infinite distance-transitive graphs of finite valency, Combinatorica, 2, 63-69, (1982) · Zbl 0492.05036
[20] Moon, A., Characterization of the odd graphs ok by parameters, Discrete math., 42, 91-97, (1982) · Zbl 0494.05035
[21] Moon, A., Characterization of the graphs of the Johnson schemes, G(3k, k) and G(3k + 1, k), J. combin. theory, ser. B, 33, 213-221, (1982) · Zbl 0506.05053
[22] Moon, A., On the uniqueness of the graphs G(n, k) of the Johnson schemes, J. combin. theory, Ser. B 33, 256-264, (1982) · Zbl 0506.05054
[23] Rolland, P.T., On the uniqueness of the tetrahedral association scheme, ph.D. thesis, (1976), City University of New York
[24] Shrikhande, S.S., On a characterization of the triangular association scheme, Ann. math. statist., 30, 39-47, (1959) · Zbl 0089.15101
[25] Shrikhande, S.S., The uniqueness of the LZ association scheme, Ann. math. statist., 30, 781-798, (1959) · Zbl 0086.34802
[26] Terwilliger, P., The diameter of bipartite distance-regular graphs, J. combin. theory, ser. B, 32, 182-188, (1982) · Zbl 0487.05038
[27] P. Terwilliger: Distance-regular graphs with girth 3 or 4, 1, J. Combin. Theory, Ser. B, to appear. · Zbl 0588.05039
[28] Terwilliger, P., Distance-regular graphs and generalisations, ph.D. thesis, (1982), University of Illinois at Urbana
[29] Terwilliger, P., Distance-regular graphs and (s, C, a, k)-graphs, J. combin. theory, ser. B, 34, 151-164, (1983) · Zbl 0511.05052
[30] P. Terwilliger: The Johnson graph J(d, n) is unique if (d, n) A (2, 8), preprint. · Zbl 0587.05038
[31] Yamamoto, S.; Fujii, Y.; Hamada, N., Composition of some series of association algebras, J. sci. Hiroshima univ., Ser. A-129, 181-215, (1965) · Zbl 0166.15205
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.