TOPICS
Search

Graph Switching


Graph switching is a collective term for operations that produce a new graph from a given graph by changing its adjacencies according to a prescribed rule. It does not refer to a unique operation.

The unqualified term "switching" often denotes Seidel switching, which exchanges edges and nonedges between a chosen subset S of the vertex set V and V\S (Seidel 1974).

Godsil-McKay switching chooses a vertex subset W that induces a regular graph and for which every vertex outside W has 0, 1/2|W|, or |W| neighbors in W. For each vertex having 1/2|W| neighbors in W, its neighbors and nonneighbors in W are interchanged. The resulting graph is cospectral with the original graph (Abiad et al. 2019).

Degree-preserving edge switching, also called a 2-switch, replaces two vertex-disjoint edges by one of the other two pairings of their four endpoints, provided the replacement edges are not already present. This operation preserves the degree sequence and is the switching used in the definitions of switchable and unswitchable graphs (Mukhopadhyay et al. 2023).


See also

Seidel Switching, Switchable Graph, Switching Class, Two-Graph, Unswitchable Graph

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

Abiad, A.; Butler, S.; and Haemers, W. H. "Graph Switching, 2-Ranks, and Graphical Hadamard Matrices." Disc. Math. 342, 2850-2855, 2019. https://doi.org/10.1016/j.disc.2018.11.022.Mukhopadhyay, A.; John, D.; and Vasudevan, S. "Recognizing and Generating Unswitchable Graphs." 12 Apr 2023. https://arxiv.org/abs/2304.12381.Seidel, J. J. "Graphs and Two-Graphs." In Proc. 5th Southeast Conf. Comb., Graph Th., Comp. (Ed. F. Hoffman et al.). Winnipeg, Canada: Utilitas Mathematica Pub., pp. 125-143, 1974.

Cite this as:

Weisstein, Eric W. "Graph Switching." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphSwitching.html

Subject classifications