| Title:
|
On graphs with maximum size in their switching classes (English) |
| Author:
|
Kozerenko, Sergiy |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
56 |
| Issue:
|
1 |
| Year:
|
2015 |
| Pages:
|
51-61 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
Seidel switching |
| Keyword:
|
switching class |
| Keyword:
|
maximum size graph |
| MSC:
|
05C75 |
| MSC:
|
05C99 |
| idZBL:
|
Zbl 06433805 |
| idMR:
|
MR3311577 |
| DOI:
|
10.14712/1213-7243.015.105 |
| . |
| Date available:
|
2015-03-10T17:35:43Z |
| Last updated:
|
2017-04-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/144188 |
| . |
| Reference:
|
[1] Cameron P.J.: Two-graphs and trees.Discrete Math. 127 (1994), 63–74. Zbl 0802.05042, MR 1273592, 10.1016/0012-365X(92)00468-7 |
| Reference:
|
[2] Colbourn C.J., Corneil D.G.: On deciding switching equivalence of graphs.Discrete Appl. Math. 2 (1980), 181–184. Zbl 0438.05054, MR 0588697, 10.1016/0166-218X(80)90038-4 |
| Reference:
|
[3] Ehrenfeucht A., Hage J., Harju T., Rozenberg G.: Pancyclicity in switching classes.Inform. Process. Lett. 73 (2000), 153–156. MR 1755051, 10.1016/S0020-0190(00)00020-X |
| Reference:
|
[4] Hage J.: Structural aspects of switching classes.PhD thesis, Leiden Institute of Advanced Computer Science, 2001. |
| Reference:
|
[5] Hage J., Harju T.: Acyclicity of switching classes.Europ. J. Combin. 19 (1998), 321–327. Zbl 0905.05057, MR 1621017, 10.1006/eujc.1997.0191 |
| Reference:
|
[6] Harries D., Liebeck H.: Isomorphisms in switching classes of graphs.J. Austral. Math. Soc. 26 (1978), 475–486. Zbl 0411.05044, MR 0520101, 10.1017/S144678870001199X |
| Reference:
|
[7] Hertz A.: On perfect switching classes.Discrete Appl. Math. 89 (1998), 263–267. Zbl 0930.05044, MR 1663113, 10.1016/S0166-218X(98)00134-6 |
| Reference:
|
[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 |
| Reference:
|
[9] Krasikov I.: A note on the vertex-switching reconstruction.Internat. J. Math. Math. Sci. 11 (1988), 825–827. Zbl 0663.05046, MR 0959466, 10.1155/S0161171288001012 |
| Reference:
|
[10] Krasikov I., Roditty Y.: Switching reconstructions and diophantine equations.J. Combin. Theory Ser. B 54 (1992), 189–195. MR 1152446, 10.1016/0095-8956(92)90050-8 |
| Reference:
|
[11] van Lint J.H., Seidel J.J.: Equilateral point sets in elliptic geometry.Indag. Math. 28 (1966), 335–348. Zbl 0138.41702, MR 0200799, 10.1016/S1385-7258(66)50038-5 |
| Reference:
|
[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. Zbl 0275.05125, MR 0427128, 10.1137/0128070 |
| Reference:
|
[13] Ore O: Theory of Graphs.Amer. Math. Soc., Providence, Rhode Island, 1962. Zbl 0484.05030 |
| Reference:
|
[14] Seidel J.J.: A survey of two-graphs.Proc. Int. Coll. 1 (1973), 481–511. Zbl 0352.05016, MR 0550136 |
| Reference:
|
[15] Stanley R.P.: Reconstruction from vertex-switching.J. Combin. Theory Ser. B 38 (1985), 132–138. Zbl 0572.05046, MR 0787322, 10.1016/0095-8956(85)90078-4 |
| . |
