There are four strongly regular graphs with parameters ,
one of them being the triangular graph
. 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).
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.