## Sergiy Kozerenko

*On graphs with maximum size in their switching classes*

Comment.Math.Univ.Carolin. 56,1 (2015) 51-61.**Abstract:**In his PhD thesis [{\it Structural aspects of switching classes\/}, Leiden Institute of Advanced Computer Science, 2001] Hage posed the following problem: ``characterize the maximum size graphs in switching classes''. These are called \emph{s-maximal} graphs. In this paper, we study the properties of such graphs. In particular, we show that any graph with sufficiently large minimum degree is s-maximal, we prove that join of two s-maximal graphs is also an s-maximal graph, we give complete characterization of triangle-free s-maximal graphs and non-hamiltonian s-maximal graphs. We also obtain other interesting properties of s-maximal graphs.

**Keywords:** Seidel switching; switching class; maximum size graph

**DOI:** DOI 10.14712/1213-7243.015.105

**AMS Subject Classification:** 05C75 05C99

PDF