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).

Equivalently, T_n is the graph complement of the Kneser graph K(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, Kneser 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.DistanceRegular.org. "Johnson Graphs J(n,m)." https://www.math.mun.ca/distanceregular/indexes/johnsongraphs.html.Hoffman, A. J. "On the Uniqueness of the Triangular Association Scheme." Ann. Math. Stat. 31, 492-497, 1960.House of Graphs. Triangular Graphs. Octahedron K2,2,2, Singleton Graph, Triangle K3, L(K5), L(K6), L(K7), L(K8), L(K9), and L(K10).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 Resource. https://mathworld.wolfram.com/TriangularGraph.html

Subject classifications