In the
mathematical
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
field of
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, the Chang graphs are three 12-
regular undirected graph
In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...
s, each with 28 vertices and 168 edges. They are
strongly regular, with the same parameters and
spectrum
A spectrum (: spectra or spectrums) is a set of related ideas, objects, or properties whose features overlap such that they blend to form a continuum. The word ''spectrum'' was first used scientifically in optics to describe the rainbow of co ...
as the
line graph
In the mathematics, mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edge (graph theory), edges of . is constructed in the following way: for each edge i ...
''L''(''K''
8) of the
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...
''K''
''8''.
Each of these three graphs may be obtained by
graph switching from ''L''(''K''
8). That is, a subset ''S'' of the vertices of ''L''(''K''
8) is chosen, each edge that connects a vertex in ''S'' with a vertex not in ''S'' is deleted from ''L''(''K''
8), and an edge is added for each pair of vertices (with again one in ''S'' and one not in ''S'') that were not already connected by an edge. Among the graphs that can be generated in this way, three of them are the Chang graphs.
The Chang graphs are named after Chang Li-Chien, who proved that, with only these exceptions, every line graph of a complete graph is uniquely determined by its parameters as a strongly regular graph.
[.]
See also
*
Shrikhande graph
In the mathematical field of graph theory, the Shrikhande graph is a graph discovered by S. S. Shrikhande in 1959.. It is a strongly regular graph with 16 vertices and 48 edges, with each vertex having degree 6. Every pair of nodes has ...
, a similar exception to the uniqueness of the strongly regular graphs
References
External links
Weisstein, Eric W. "Chang Graphs." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/ChangGraphs.htmlNadia Hamoud, "The Chang graphs"
{{DEFAULTSORT:Chang Graphs
Individual graphs
Regular graphs
Strongly regular graphs