Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
Seidel switching; switching class; maximum size graph
Seidel switching; switching class; maximum size graph
Summary:
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.
References:
[1] Cameron P.J.: Two-graphs and trees. Discrete Math. 127 (1994), 63–74. DOI 10.1016/0012-365X(92)00468-7 | MR 1273592 | Zbl 0802.05042
[2] Colbourn C.J., Corneil D.G.: On deciding switching equivalence of graphs. Discrete Appl. Math. 2 (1980), 181–184. DOI 10.1016/0166-218X(80)90038-4 | MR 0588697 | Zbl 0438.05054
[3] Ehrenfeucht A., Hage J., Harju T., Rozenberg G.: Pancyclicity in switching classes. Inform. Process. Lett. 73 (2000), 153–156. DOI 10.1016/S0020-0190(00)00020-X | MR 1755051
[4] Hage J.: Structural aspects of switching classes. PhD thesis, Leiden Institute of Advanced Computer Science, 2001.
[5] Hage J., Harju T.: Acyclicity of switching classes. Europ. J. Combin. 19 (1998), 321–327. DOI 10.1006/eujc.1997.0191 | MR 1621017 | Zbl 0905.05057
[6] Harries D., Liebeck H.: Isomorphisms in switching classes of graphs. J. Austral. Math. Soc. 26 (1978), 475–486. DOI 10.1017/S144678870001199X | MR 0520101 | Zbl 0411.05044
[7] Hertz A.: On perfect switching classes. Discrete Appl. Math. 89 (1998), 263–267. DOI 10.1016/S0166-218X(98)00134-6 | MR 1663113 | Zbl 0930.05044
[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. Zbl 1283.68164
[9] Krasikov I.: A note on the vertex-switching reconstruction. Internat. J. Math. Math. Sci. 11 (1988), 825–827. DOI 10.1155/S0161171288001012 | MR 0959466 | Zbl 0663.05046
[10] Krasikov I., Roditty Y.: Switching reconstructions and diophantine equations. J. Combin. Theory Ser. B 54 (1992), 189–195. DOI 10.1016/0095-8956(92)90050-8 | MR 1152446
[11] van Lint J.H., Seidel J.J.: Equilateral point sets in elliptic geometry. Indag. Math. 28 (1966), 335–348. DOI 10.1016/S1385-7258(66)50038-5 | MR 0200799 | Zbl 0138.41702
[12] Mallows C.L., Sloane N.J.A.: Two-graphs, switching classes and Euler graphs are equal in number. SIAM J. Appl. Math. 28 (1975), 876–880. DOI 10.1137/0128070 | MR 0427128 | Zbl 0275.05125
[13] Ore O: Theory of Graphs. Amer. Math. Soc., Providence, Rhode Island, 1962. Zbl 0484.05030
[14] Seidel J.J.: A survey of two-graphs. Proc. Int. Coll. 1 (1973), 481–511. MR 0550136 | Zbl 0352.05016
[15] Stanley R.P.: Reconstruction from vertex-switching. J. Combin. Theory Ser. B 38 (1985), 132–138. DOI 10.1016/0095-8956(85)90078-4 | MR 0787322 | Zbl 0572.05046
Search
Partner of
