The three Chang graphs are the strongly regular graphs with parameters
other than the triangular graph
, and are illustrated above (the graph drawings in this figure
are degenerate at the center: four graph
vertices are assigned the same coordinates and
therefore appear as a single central vertex).
In the illustration above, the upper row illustrates the Seidel switching construction. In each diagram, the vertices
in the switching set
are green. Red edges in the edge
cut between
and its complement set in the vertex
set of
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 is the line graph of
the complete graph
, so each vertex of
corresponds to an edge
of
, with adjacent
vertices of
corresponding exactly to edges of
that share an endpoint. Consequently, the green vertex
sets may also be regarded as edge sets of
. 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
determined by the three switching sets:
, four isolated
vertices, and
.
The four matching edges are pairwise disjoint
in
, so no two of the corresponding vertices of
are adjacent, explaining
the isolated vertices in the middle lower panel.
For the first and third switching sets, every vertex of is incident
with two selected edges; for the second, every vertex
is incident with one. It follows that every vertex
of
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 . All of them have graph spectrum
, so none is determined
by spectrum.
The Chang graphs are distance-regular with intersection array but are not distance-transitive.
They are pancyclic.
None of the Chang graphs has a nontrivial voltage graph presentation, an LCF notation of order , or a bilaterally symmetric LCF notation.
The Chang graphs are implemented in the Wolfram Language as GraphData["Chang", n
] for
, 2, 3.