TOPICS
Search

Chang Graphs


ChangGraphs

There are four strongly regular graphs with parameters (nu,k,lambda,mu)=(28,12,6,4), one of them being the triangular graph T_8. The other three such graphs are known as the Chang graphs, illustrated above (the graph embeddings in this figure are degenerate at the center: four graph vertices are assigned the same coordinates and therefore appear as a single central vertex).

ChangGraphsSwitching

In the illustration above, the upper row illustrates the Seidel switching construction. In each diagram, the vertices in the switching set S are green. Red edges in the edge cut between S and its complement set in the vertex set of T_8 are removed by edge deletion, while translucent blue edges represent non-edges between the same two parts that are added. Black edges have both endpoints in the same part and remain unchanged.

The triangular graph T_8=L(K_8) is the line graph of the complete graph K_8, so each vertex of T_8 corresponds to an edge of K_8, with adjacent vertices of T_8 corresponding exactly to edges of K_8 that share an endpoint. Consequently, the green vertex sets may also be regarded as edge sets of K_8. In left-to-right order, these edge sets form disjoint 3- and 5-cycles, a perfect matching, and an 8-cycle, respectively. The lower row shows the vertex-induced subgraphs of T_8 determined by the three switching sets: C_3⊔C_5, four isolated vertices, and C_8. The four matching edges are pairwise disjoint in K_8, so no two of the corresponding vertices of T_8 are adjacent, explaining the isolated vertices in the middle lower panel.

For the first and third switching sets, every vertex of K_8 is incident with two selected edges; for the second, every vertex is incident with one. It follows that every vertex of T_8 is adjacent to exactly half the vertices in the opposite part of the switching partition. The switch therefore deletes and adds the same number of incident edges at every vertex, so every switched graph remains a regular graph of degree 12. The three resulting pairwise nonisomorphic graphs are the Chang graphs.

The Chang graphs are cospectral with the triangular graph T_8. All of them have graph spectrum (-2)^(20)4^712^1, so none is determined by spectrum.

The Chang graphs are distance-regular with intersection array {12,5;1,4} but are not distance-transitive. They are pancyclic.

None of the Chang graphs has a nontrivial voltage graph presentation, an LCF notation of order >1, or a bilaterally symmetric LCF notation.

The Chang graphs are implemented in the Wolfram Language as GraphData[{"Chang", n}] for n=1, 2, 3.


See also

Determined by Spectrum, Paulus Graphs, Strongly Regular Graph, Triangular Graph

Explore with Wolfram|Alpha

References

Brouwer, A. E. "Chang Graphs." https://aeb.win.tue.nl/graphs/Chang.html.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, pp. 105-106, 1989.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. "Association Schemes 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. "Chang Graphs (3 Graphs)." https://www.math.mun.ca/distanceregular/graphs/chang.html.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, p. 259, 2001.Hoffman, A. J. "On the Uniqueness of the Triangular Association Scheme." Ann. Math. Stat. 31, 492-497, 1960.House of Graphs. Chang Graphs. Chang Graph 1, Chang Graph 2, and Chang Graph 3.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

Chang Graphs

Cite this as:

Weisstein, Eric W. "Chang Graphs." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ChangGraphs.html

Subject classifications