TOPICS
Search

Triangular Graph

TriangularGraphs

The triangular graph T_n=L(K_n) is the line graph of the complete graph K_n (Brualdi and Ryser 1991, p. 152).

The vertices of T_n may be identified with the 2-subsets of {1,2,...,n} that are adjacent iff the 2-subsets have a nonempty intersection (Ball and Coxeter 1987, p. 304; Brualdi and Ryser 1991, p. 152), namely the Johnson graph J(n,2).

The triangular graphs are distance-regular and geometric.

Chang (1959, 1960) and Hoffman (1960) showed that if G is a strongly regular graph on the parameters (nu,k,lambda,mu)=(n(n-1)/2,2(n-2),n-2,4) with n>=4, then if n!=8, G is isomorphic to the triangular graph T_n. If n=8, then G is isomorphic to one of three graphs known as the Chang graphs or to T_8 (Brualdi and Ryser 1991, p. 152).

T_8 is also cospectral with the Chang graphs, meaning that none of these four graphs is determined by spectrum.

The independence number of a triangular graph is given by

alpha(T_n)=|_n/2_|,
(1)

where |_x_| is the floor function. Its chromatic number is given by

chi(T_n)={n for n odd; n-1 for n even.
(2)

See also

Chang Graphs, Cospectral Graphs, Determined by Spectrum, Johnson Graph, Lattice Graph, Square Graph, Triangle Graph, Triangular Grid Graph

Explore with Wolfram|Alpha

References

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, p. 304, 1987.Brouwer, A. E. and van Lint, J. H. "Strongly Regular Graphs and Partial Geometries." In Enumeration and Design: Papers from the conference on combinatorics held at the University of Waterloo, Waterloo, Ont., June 14-July 2, 1982 (Ed. D. M. Jackson and S. A. Vanstone). Toronto, Canada: Academic Press, pp. 85-122, 1984.Brualdi, R. and Ryser, H. J. Combinatorial Matrix Theory. New York: Cambridge University Press, p. 152, 1991.Chang, L.-C. "The Uniqueness and Non-Uniqueness of the Triangular Association Scheme." Sci. Record Peking Math. Soc. 3, 604-613, 1959.Chang, L.-C. "Associations of Partially Balanced Designs with Parameters v=28, n_1=12, n_2=15, and p_(11)^2=4." Sci. Record Peking Math. 4, 12-18, 1960.Hoffman, A. J. "On the Uniqueness of the Triangular Association Scheme." Ann. Math. Stat. 31, 492-497, 1960.van Dam, E. R. and Haemers, W. H. "Which Graphs Are Determined by Their Spectrum?" Lin. Algebra Appl. 373, 139-162, 2003.

Referenced on Wolfram|Alpha

Triangular Graph

Cite this as:

Weisstein, Eric W. "Triangular Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/TriangularGraph.html

Subject classifications