On graphs with maximum size in their switching classes

Sergiy Kozerenko

Commentationes Mathematicae Universitatis Carolinae (2015)

  • Volume: 56, Issue: 1, page 51-61
  • ISSN: 0010-2628

Abstract

top
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.

How to cite

top

Kozerenko, Sergiy. "On graphs with maximum size in their switching classes." Commentationes Mathematicae Universitatis Carolinae 56.1 (2015): 51-61. <http://eudml.org/doc/269871>.

@article{Kozerenko2015,
abstract = {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.},
author = {Kozerenko, Sergiy},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {Seidel switching; switching class; maximum size graph; Seidel switching; switching class; maximum size graph},
language = {eng},
number = {1},
pages = {51-61},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {On graphs with maximum size in their switching classes},
url = {http://eudml.org/doc/269871},
volume = {56},
year = {2015},
}

TY - JOUR
AU - Kozerenko, Sergiy
TI - On graphs with maximum size in their switching classes
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2015
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 56
IS - 1
SP - 51
EP - 61
AB - 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.
LA - eng
KW - Seidel switching; switching class; maximum size graph; Seidel switching; switching class; maximum size graph
UR - http://eudml.org/doc/269871
ER -

References

top
  1. Cameron P.J., 10.1016/0012-365X(92)00468-7, Discrete Math. 127 (1994), 63–74. Zbl0802.05042MR1273592DOI10.1016/0012-365X(92)00468-7
  2. Colbourn C.J., Corneil D.G., 10.1016/0166-218X(80)90038-4, Discrete Appl. Math. 2 (1980), 181–184. Zbl0438.05054MR0588697DOI10.1016/0166-218X(80)90038-4
  3. Ehrenfeucht A., Hage J., Harju T., Rozenberg G., 10.1016/S0020-0190(00)00020-X, Inform. Process. Lett. 73 (2000), 153–156. MR1755051DOI10.1016/S0020-0190(00)00020-X
  4. Hage J., Structural aspects of switching classes, PhD thesis, Leiden Institute of Advanced Computer Science, 2001. 
  5. Hage J., Harju T., 10.1006/eujc.1997.0191, Europ. J. Combin. 19 (1998), 321–327. Zbl0905.05057MR1621017DOI10.1006/eujc.1997.0191
  6. Harries D., Liebeck H., 10.1017/S144678870001199X, J. Austral. Math. Soc. 26 (1978), 475–486. Zbl0411.05044MR0520101DOI10.1017/S144678870001199X
  7. Hertz A., 10.1016/S0166-218X(98)00134-6, Discrete Appl. Math. 89 (1998), 263–267. Zbl0930.05044MR1663113DOI10.1016/S0166-218X(98)00134-6
  8. Jelínková E., Suchý O., Hliněny P., Kratochvíl J., Parameterized problems related to Seidel's switching, Discrete Math. Theor. Comp. Sci. 13 (2011), no. 2, 19–44. Zbl1283.68164
  9. Krasikov I., 10.1155/S0161171288001012, Internat. J. Math. Math. Sci. 11 (1988), 825–827. Zbl0663.05046MR0959466DOI10.1155/S0161171288001012
  10. Krasikov I., Roditty Y., 10.1016/0095-8956(92)90050-8, J. Combin. Theory Ser. B 54 (1992), 189–195. MR1152446DOI10.1016/0095-8956(92)90050-8
  11. van Lint J.H., Seidel J.J., 10.1016/S1385-7258(66)50038-5, Indag. Math. 28 (1966), 335–348. Zbl0138.41702MR0200799DOI10.1016/S1385-7258(66)50038-5
  12. Mallows C.L., Sloane N.J.A., 10.1137/0128070, SIAM J. Appl. Math. 28 (1975), 876–880. Zbl0275.05125MR0427128DOI10.1137/0128070
  13. Ore O, Theory of Graphs, Amer. Math. Soc., Providence, Rhode Island, 1962. Zbl0484.05030
  14. Seidel J.J., A survey of two-graphs, Proc. Int. Coll. 1 (1973), 481–511. Zbl0352.05016MR0550136
  15. Stanley R.P., 10.1016/0095-8956(85)90078-4, J. Combin. Theory Ser. B 38 (1985), 132–138. Zbl0572.05046MR0787322DOI10.1016/0095-8956(85)90078-4

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.