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