Geodesic
On graphs with maximum size in their switching classes
Commentationes Mathematicae Universitatis Carolinae, Tome 56 (2015) no. 1, pp. 51-61.

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

In his PhD thesis [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 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.
DOI : 10.14712/1213-7243.015.105
Classification : 05C75, 05C99
Keywords: Seidel switching; switching class; maximum size graph 
@article{10_14712_1213_7243_015_105,
     author = {Kozerenko, Sergiy},
     title = {On graphs with maximum size in their switching classes},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     pages = {51--61},
     publisher = {mathdoc},
     volume = {56},
     number = {1},
     year = {2015},
     doi = {10.14712/1213-7243.015.105},
     mrnumber = {3311577},
     zbl = {06433805},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14712/1213-7243.015.105/}
}
TY  - JOUR
AU  - Kozerenko, Sergiy
TI  - On graphs with maximum size in their switching classes
JO  - Commentationes Mathematicae Universitatis Carolinae
PY  - 2015
SP  - 51
EP  - 61
VL  - 56
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.14712/1213-7243.015.105/
DO  - 10.14712/1213-7243.015.105
LA  - en
ID  - 10_14712_1213_7243_015_105
ER  - 
%0 Journal Article
%A Kozerenko, Sergiy
%T On graphs with maximum size in their switching classes
%J Commentationes Mathematicae Universitatis Carolinae
%D 2015
%P 51-61
%V 56
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.14712/1213-7243.015.105/
%R 10.14712/1213-7243.015.105
%G en
%F 10_14712_1213_7243_015_105
Kozerenko, Sergiy. On graphs with maximum size in their switching classes. Commentationes Mathematicae Universitatis Carolinae, Tome 56 (2015) no. 1, pp. 51-61. doi : 10.14712/1213-7243.015.105. http://geodesic.mathdoc.fr/articles/10.14712/1213-7243.015.105/

Cité par Sources :