Home

Switching Classes

I wrote my PhD (download) on the subject of switching classes from the combinatorial, algorithmic and algebraic side. The results in the PhD are mostly based on the list of papers below, but include some new results new. Additionally, the proofs are more detailed and there are quite a few examples to explain the theory involved.

What are switching classes?

Concisely put: switching classes are equivalence classes of undirected graphs. Two graphs are equivalent if they can be switched into each other. Given a graph G on a vertex set V, one can obtain a switch of G by selecting a subset of the vertices, call that set S, and by then removing all edges between S and V-S in G that exist, and by inserting all edges between S and V-S that do not.

Much more general models exist in which we consider directed graphs labelled with elements of a group, under a certain "reversibility" constraint. This is the subject of the second part of my thesis.

Publications on switching classes

I (co-)wrote the following papers on switching classes.

A. Ehrenfeucht, J. Hage, T. Harju, G. Rozenberg.: Pancyclicity of switching classes.
Information Processing Letters 73 (2000) 153-156.
technical report .
A. Ehrenfeucht, J. Hage, T. Harju, G. Rozenberg.: Complexity Issues in Switching of Graphs.
In: Theory and Applications of Graph Transformations - TAGT'98 (H. Ehrig, G. Engels, H.-J. Kreowski, G. Rozenberg, eds.), Lecture Notes in Computer Science, v. 1764, Springer Verlag, 59-70, 2000.
J. Hage, T. Harju.: The size of switching classes with skew gains.
Discrete Mathematics 215 (2000) 81-92.
technical report .
J. Hage, T. Harju.: A characterization of acyclic switching classes using forbidden subgraphs.
LIACS Technical Report TR 00-05, March 2000.
J. Hage.: The Membership Problem for Switching Classes of Skew Gains.
Fundamenta Informaticae 39 (1999) 375--387.
technical report .
J. Hage, T. Harju.: Acyclicity of Switching Classes.
Eur. Jnl. of Combinatorics 19 (1998) 321-327.
technical report .
J. Hage, T. Harju.: The Size of 2-Classes in Group Labeled 2-Structures.
Leiden University Technical Report 96-17, 1996.

Of course, there are many more such publications by other authors. A comprehensive listing can be found in the form of Zaslavsky's dynamic library which can be obtained through here.

Another useful link is the following link to the site of Ted Spence which has files listing generators of switching classes up to isomorphism and complementation.

A PhD thesis on Switching Classes

You can download the complete book (152 pages) in PDF-format by clicking here. I appreciate it if you e-mail me when you download it. The book contains a few mistakes, which I have listed below including a few improvements as well. If you have found any errors, then please let me know by mailing me. If you see something that you suspect might be wrong, then it is wise to check here to see whether anybody has had the same problem. I have omitted a few very innocent mistakes, typo's like fnuction instead of function. It goes without saying that in the dowloadable version of the thesis, all listed mistakes have been corrected.

p.29, first line of Section 3.1. "iniators" ==> "initiators"
p.30,-7. X is not constant on \sigma, but \sigma is constant on X
p.35,+5. Lemma 3.13 ==> Theorem 3.13
p.35, in Example 3.16 replace "We obtain....respectively" with "We obtain a triangle with two leaves at one of its vertices, an edge with three isolated vertices, and a $C_4$ with a leaf at one of its vertices, respectively."
p.35, 2nd line of the proof of Thm.3.17. "odd order" ==> "odd degree"
p.36,+2. put the intersection between | and |
p.36,+4. "A is even" ==> "|A| is even".
p.37,+14. Lemma 3.13 ==> Theorem 3.13
p.37,+22. "u \in T" ==> "u \in V"
p.38, first line of Section 3.4.1. "Lemma 3.8" ==> "Corollary 3.8"
p.40, Corollary 3.25, "(n-d(n))+1+" ==> "(n-1-d(n))+1+"
p.41, line 7 of the proof of Thm.3.29. "NP-complete by" ==> "NP-complete and so the problem is NP-complete by"
p.45, Corollary 3.39. "NP-complete" ==> "NP-hard"
p.49, line before Corollary 4.3. K_{n,n} ==> K_{n/2,n/2}
p.49, proof of Corollary 4.4. "Theorem 3.13" ==> "Theorem 3.14" which is clearer
p.50, Lemma 4.6. "an acyclic graph" ==> "acyclic graphs"
p.54, proof of Theorem 4.8. This proof has been optimized quite a bit, by explicitly taking care of the case p=n+2 so that a number of special cases can be dropped.
p.55, sentence above Figure 4.7. "rightmost" ==> "leftmost"
p.57, last line. Add "see Figure 4.8(b) and Figure 4.8(c) respectively"
p.67,-2. add the line "Let the selector \tau be such that (G-u)^\tau is acyclic" before the line starting with "Without restriction..."
p.68,+15. "induced (6-1)" ==> "induced (6-1')"
p.70,+9. "case (i)" --> "Claim (i) and Claim (ii)"
p.77,+7. "A. Tijdeman" ==> "R. Tijdeman"
p.85,+9 of Example 5.14. Twice "(1,0)" -> "(0,1)"
p.91,+12. "horizon" ==> "horizon u"
p.91,+13. "Lemma 3.9" -> "Lemma 5.18"
p.93, Lemma 6.3(iv). "\delta\neq id" ==> "\delta is not the identity on Z(\Gamma)"
p.94,+12. "take a = 1_\Gamma" ==> "take g(uv) = 1_\Gamma"
p.94,-4. "thus \alpha_g(\tau) is uniquely" ==> "thus \tau is uniquely"-->
p.94-95. Theorem 6.6 is incorrect. It has been modified.
p.96, line 1 of the proof of Theorem 6.10. "Lemma 5.18" ==> "Lemma 6.5"
p.99,-10. "also g^\sigma = g" ==> "also g_T^\sigma = g_T"
p.100, last sentence of the proof. For clarity, "Thus," ==> "Thus, Stab(\hat{g}) = "
p.100,-15. "A^2(\hat{g})" ==> "A(\hat{g}-2)"
p.100,-14. "[\hat{g}]" ==> "|[\hat{g}]|"
p.100,-13. "[g]" ==> "|[g]|"
p.100,-2. "A^2(\hat{g})" ==> "A(\hat{g}-2)"
p.103,+13. "Lemma 5.18" ==> "Corollary 5.19"
p.112, Example 7.27. Add "(see also Example 6.18)" at the end of the line ending with "is indeed the case"
p.114,-6. "\Gamma" ==> "\gamma"
p.114,-2. "In that sense Theorem 7.30" ==> "In that sense the proof of Theorem 7.30"
p.114,-1. "the one corresponding" ==> "the corresponding"
p.121, last line of the proof of Lemma A.3. Remove the superfluous "|" following "m^{p+1}"
p.129, 11 of Section A.4. "S^k_q" ==> "S(k,q)"
p.129, 12 of Section A.4. "to indicate the value x_j" ==> "to indicate the value x_{j+1}"
p.130,+10. "Because 1 = \rho(6,54)" ==> "Because 1=\rho(6,48) (note that 130 is the 48th leaf in the tree of Figure A.6)"
p.130,-6, "p=\rho(k,l)" ==> "p=\rho(k,l+1)"
p.131,-5, add "(in fact, they would be number 47 and 48 in that sequence)"

Whether you have a copy of the Stellingen or not, you still might want to download this version. It is the same file as I sent to the company which printed the book, but they used buggy software on an older version and it came out witout the necessary math minus signs.

Switching in practice

In the area below you can play a little with Switching in its most simple form. By adding nodes and switching the right sets at the right time, you can make any graph. Try it! Clicking on the canvas adds nodes, clicking on a node moves it into the switching set (and again, removes it). You can also move nodes by dragging them, and use the Clear and Switch buttons.