The triangular graph is the line graph of the complete graph (Brualdi and Ryser 1991, p. 152).
The vertices of may be identified with the 2-subsets of 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 .
The triangular graphs are distance-regular and geometric.
Chang (1959, 1960) and Hoffman (1960) showed that if is a strongly regular graph on the parameters with , then if , is isomorphic to the triangular graph . If , then is isomorphic to one of three graphs known as the Chang graphs or to (Brualdi and Ryser 1991, p. 152).
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
|
(1) |
where is the floor function. Its chromatic number is given by
|
(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 , , , and ." 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
Cite this as:
Weisstein, Eric W. "Triangular Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TriangularGraph.html