Links between two semisymmetric graphs on 112 vertices via association schemes. (English) Zbl 1244.05235
Summary: This paper provides a model of the use of computer algebra experimentation in algebraic graph theory. Starting from the semisymmetric cubic graph \(\mathcal L\) on 112 vertices, we embed it into another semisymmetric graph \(\mathcal N\) of valency 15 on the same vertex set. In order to consider systematically the links between \(\mathcal L\) and \(\mathcal N\), a number of combinatorial structures are involved and related coherent configurations are investigated. In particular, the construction of the incidence double cover of directed graphs is exploited.
As a natural by-product of the approach presented here, a number of new interesting (mostly non-Schurian) association schemes on 56, 112 and 120 vertices are introduced and briefly discussed. We use computer algebra system GAP (including GRAPE and nauty), as well as computer package COCO.
As a natural by-product of the approach presented here, a number of new interesting (mostly non-Schurian) association schemes on 56, 112 and 120 vertices are introduced and briefly discussed. We use computer algebra system GAP (including GRAPE and nauty), as well as computer package COCO.
MSC:
| 05E30 | Association schemes, strongly regular graphs |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 68W30 | Symbolic computation and algebraic computation |
Keywords:
Nikolaev graph; dejter graph; semisymmetric graph; Ljubljana graph; double cover; association scheme; computer algebra; deza graph; overlarge set of designsReferences:
| [1] | Babai, L., The forbidden sidetrip, (People & Ideas in Theoretical Computer Science. People & Ideas in Theoretical Computer Science, Springer Ser. Discrete Math. Theor. Comput. Sci. (1999), Springer: Springer Singapore), 1-31 · Zbl 0932.01038 |
| [2] | Bannai, E.; Ito, T., Algebraic Combinatorics. I. Association Schemes (1984), The Benjamin/Cummings Publishing Co. Inc.: The Benjamin/Cummings Publishing Co. Inc. Menlo Park, CA, xxiv+425 pp. ISBN: 0-8053-0490-8, 05-01 · Zbl 0555.05019 |
| [3] | Betten, D., Geometrische Permutationsgruppen, Mitt. Math. Ges. Hamburg, 10, 5, 317-324 (1977) · Zbl 0425.20030 |
| [4] | Biggs, N., Algebraic Graph Theory (1993), Cambridge Mathematical Library. Cambridge University Press: Cambridge Mathematical Library. Cambridge University Press Cambridge |
| [5] | Borges, J.; Dejter, I. J., On perfect dominating sets in hypercubes and their complements, J. Combin. Math. Combin. Comput., 20, 161-173 (1996) · Zbl 0852.05070 |
| [6] | Bouwer, I. Z., An edge but not vertex transitive cubic graph, Canad. Math. Bull., 11, 533-535 (1968) · Zbl 0182.58102 |
| [7] | Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-regular graphs, (Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 18 (1989), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0747.05073 |
| [8] | Brouwer, A. E.; Ivanov, A. V.; Klin, M. H., Some new strongly regular graphs, Combinatorica, 9, 4, 339-344 (1989), URL: http://dx.doi.org/10.1007/BF02125346 · Zbl 0709.05040 |
| [9] | Brouwer, A. E.; Dejter, I. J.; Thomassen, C., Highly symmetric subgraphs of hypercubes, J. Algebraic Combin., 2, 1, 25-29 (1993), URL: http://dx.doi.org/10.1023/A:1022472513494 · Zbl 0788.05041 |
| [10] | Cameron, P. J., Permutation groups, (London Mathematical Society Student Texts, vol. 45 (1999), Cambridge University Press: Cambridge University Press Cambridge), URL: http://dx.doi.org/10.1017/CBO9780511623677 · Zbl 1091.20002 |
| [11] | Colbourn, C. J.; Rosa, A., Triple systems, (Oxford Mathematical Monographs (1999), The Clarendon Press Oxford University Press: The Clarendon Press Oxford University Press New York) · Zbl 0607.05014 |
| [12] | Conder, M.; Malnič, A.; Marušič, D.; Pisanski, T.; Potočnik, P., The edge-transitive but not vertex-transitive cubic graph on 112 vertices, J. Graph Theory, 50, 1, 25-42 (2005), URL: http://dx.doi.org/10.1002/jgt.20089 · Zbl 1069.05039 |
| [13] | Conder, M.; Malnič, A.; Marušič, D.; Potočnik, P., A census of semisymmetric cubic graphs on up to 768 vertices, J. Algebraic Combin., 23, 3, 255-294 (2006), URL: http://dx.doi.org/10.1007/s10801-006-7397-3 · Zbl 1089.05032 |
| [14] | Coxeter, H. S.M., Self-dual configurations and regular graphs, Bull. Amer. Math. Soc., 56, 413-455 (1950) · Zbl 0040.22803 |
| [15] | Dejter, I. J., On symmetric subgraphs of the \(7\)-cube: an overview, Discrete Math., 124, 1-3, 55-66 (1994), Graphs and combinatorics (Qawra, 1990). URL: http://dx.doi.org/10.1016/0012-365X(92)00128-E · Zbl 0792.05137 |
| [16] | Dejter, I. J., Symmetry of factors of the \(7\)-cube Hamming shell, J. Combin. Des., 5, 4, 301-309 (1997), URL: http://dx.doi.org/10.1002/(SICI)1520-6610(1997)5:4<301::AID-JCD5>3.3.CO;2-B · Zbl 0912.05050 |
| [17] | Dejter, I. J.; Guan, P., Square-blocking edge subsets in hypercubes and vertex avoidance, (Graph Theory, Combinatorics, Algorithms, and Applications (San Francisco, CA, 1989) (1991), SIAM: SIAM Philadelphia, PA), 162-174 · Zbl 0755.05018 |
| [18] | Dejter, I.J., Pujol, J., 1995. Perfect domination and symmetry in hypercubes. In: Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Boca Raton, FL, vol. 111, pp. 18-32.; Dejter, I.J., Pujol, J., 1995. Perfect domination and symmetry in hypercubes. In: Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Boca Raton, FL, vol. 111, pp. 18-32. · Zbl 0896.05034 |
| [19] | Dejter, I.J., Weichsel, P.M., 1993. Twisted perfect dominating subgraphs of hypercubes. In: Proceedings of the Twenty-fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, vol.94, pp. 67-78.; Dejter, I.J., Weichsel, P.M., 1993. Twisted perfect dominating subgraphs of hypercubes. In: Proceedings of the Twenty-fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, vol.94, pp. 67-78. · Zbl 0801.05063 |
| [20] | Deza, A.; Deza, M., The ridge graph of the metric polytope and some relatives, (Polytopes: Abstract, Convex and Computational, Scarborough, ON, 1993. Polytopes: Abstract, Convex and Computational, Scarborough, ON, 1993, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 440 (1994), Kluwer Acad. Publ.: Kluwer Acad. Publ. Dordrecht), 359-372 · Zbl 0809.52017 |
| [21] | Dixon, J. D.; Mortimer, B., Permutation groups, (Graduate Texts in Mathematics, vol. 163 (1996), Springer-Verlag: Springer-Verlag New York) · Zbl 0951.20001 |
| [22] | Erickson, M.; Fernando, S.; Haemers, W. H.; Hardy, D.; Hemmeter, J., Deza graphs: a generalization of strongly regular graphs, J. Combin. Des., 7, 6, 395-405 (1999), URL: http://dx.doi.org/10.1002/(SICI)1520-6610(1999)7:6<395::AID-JCD1>3.3.CO;2-L · Zbl 0959.05122 |
| [23] | Faradžev, I. A.; Ivanov, A. A.; Klin, M. H., Galois correspondence between permutation groups and cellular rings (association schemes), Graphs Combin., 6, 4, 303-332 (1990), URL: http://dx.doi.org/10.1007/BF01787700 · Zbl 0764.05099 |
| [24] | Faradžev, I. A.; Klin, M. H., Computer package for computations with coherent configurations, (Proc. ISSAC (1991), ACM Press: ACM Press Bonn), 219-223 · Zbl 0925.20006 |
| [25] | Faradžev, I. A.; Klin, M. H.; Muzichuk, M. E., Cellular rings and groups of automorphisms of graphs, (Investigations in Algebraic Theory of Combinatorial Objects. Investigations in Algebraic Theory of Combinatorial Objects, Math. Appl. (Soviet Ser.), vol. 84 (1994), Kluwer Acad. Publ: Kluwer Acad. Publ Dordrecht), 1-152 · Zbl 0795.05073 |
| [26] | Folkman, J., Regular line-symmetric graphs, J. Combin. Theory, 3, 215-232 (1967) · Zbl 0158.42501 |
| [27] | GAP,, 2008. GAP—Groups, Algorithms, and Programming, Version 4.4.12. The GAP Group. URL: http://www.gap-system.org; GAP,, 2008. GAP—Groups, Algorithms, and Programming, Version 4.4.12. The GAP Group. URL: http://www.gap-system.org |
| [28] | Godsil, C.; Royle, G., Algebraic graph theory, (Graduate Texts in Mathematics, vol. 207 (2001), Springer-Verlag: Springer-Verlag New York) · Zbl 0968.05002 |
| [29] | Harary, F., Graph Theory (1969), Addison-Wesley Publishing Co: Addison-Wesley Publishing Co Reading, Mass.-Menlo Park, Calif.-London · Zbl 0797.05064 |
| [30] | Higman, D. G., Coherent configurations. I, Rend. Sem. Mat. Univ. Padova, 44, 1-25 (1970) · Zbl 0279.05025 |
| [31] | Higman, D. G., Coherent algebras, Linear Algebra Appl., 93, 209-239 (1987), URL: http://dx.doi.org/10.1016/S0024-3795(87)90326-0 · Zbl 0618.05014 |
| [32] | Higman, D. G., Rank 5 association schemes and triality, Linear Algebra Appl., 226/228, 197-222 (1995), URL: http://dx.doi.org/10.1016/0024-3795(95)00102-W · Zbl 0832.05099 |
| [33] | Holt, D. F., A graph which is edge transitive but not arc transitive, J. Graph Theory, 5, 2, 201-204 (1981), URL: http://dx.doi.org/10.1002/jgt.3190050210 · Zbl 0423.05020 |
| [34] | Ivanov, A. A., Computation of lengths of orbits of a subgroup in a transitive permutation group, (Investigations in Algebraic Theory of Combinatorial Objects. Investigations in Algebraic Theory of Combinatorial Objects, Math. Appl. (Soviet Ser.), vol. 84 (1994), Kluwer Acad. Publ: Kluwer Acad. Publ Dordrecht), 275-282 · Zbl 0794.20008 |
| [35] | Ivanov, A. A.; Iofinova, M. E., Biprimitive cubic graphs, (Investigations in the algebraic theory of combinatorial objects (Russian) (1985), Vsesoyuz. Nauchno-Issled. Inst. Sistem. Issled: Vsesoyuz. Nauchno-Issled. Inst. Sistem. Issled Moscow), 123-134 · Zbl 0706.05025 |
| [36] | Ivanov, A. V., On edge but not vertex transitive regular graphs, (Combinatorial Design Theory. Combinatorial Design Theory, North-Holland Math. Stud, vol. 149 (1987), North-Holland: North-Holland Amsterdam), 273-285, URL: http://dx.doi.org/10.1016/S0304-0208(08)72893-7 · Zbl 0629.05040 |
| [37] | Klin, M., 1974. Investigation of relational algebras invariant under the action of certain classes of permutation groups, Ph.D. Thesis.; Klin, M., 1974. Investigation of relational algebras invariant under the action of certain classes of permutation groups, Ph.D. Thesis. |
| [38] | Klin, M. H., Examination on the MIR-1 computer of exclusive cases in the problem of maximality of induced symmetric groups, (Computations in Algebra and Combinatorial Analysis (Russian) (1978), Akad. Nauk Ukrain. SSR Inst. Kibernet: Akad. Nauk Ukrain. SSR Inst. Kibernet Kiev), 54-72 · Zbl 0543.20003 |
| [39] | Klin, M. H., On edge but not vertex transitive graphs, (Algebraic Methods in Graph Theory, Vol. I, II, Szeged, 1978. Algebraic Methods in Graph Theory, Vol. I, II, Szeged, 1978, Math. Soc. János Bolyai, vol. 25 (1981), North-Holland: North-Holland Amsterdam), 399-403 · Zbl 0475.05041 |
| [40] | Klin, M.; Muzychuk, M.; Pech, C.; Woldar, A.; Zieschang, P.-H., Association schemes on 28 points as mergings of a half-homogeneous coherent configuration, European J. Combin., 28, 7, 1994-2025 (2007), URL: http://dx.doi.org/10.1016/j.ejc.2006.08.010 · Zbl 1145.05056 |
| [41] | Klin, M.; Muzychuk, M.; Ziv-Av, M., Higmanian rank-5 association schemes on 40 points, Michigan Math. J., 58, 1, 255-284 (2009), URL: http://dx.doi.org/10.1307/mmj/1242071692 · Zbl 1284.05339 |
| [42] | Klin, M.; Reichard, S.; Woldar, A., Siamese combinatorial objects via computer algebra experimentation, (Algorithmic Algebraic Combinatorics and Gröbner Bases (2009), Springer: Springer Berlin), 67-112, URL: http://dx.doi.org/10.1007/978-3-642-01960-9_2 · Zbl 1200.05084 |
| [43] | Klin, M.; Pech, C.; Reichard, S.; Woldar, A.; Ziv-Av, M., Examples of computer experimentation in algebraic combinatorics, Ars Math. Contemp., 3, 237-258 (2010) · Zbl 1227.05274 |
| [44] | Klin, M., Reichard, S., Woldar, A., On a simple group of order 504, its automorphism group and related combinatorial structures (in preparation).; Klin, M., Reichard, S., Woldar, A., On a simple group of order 504, its automorphism group and related combinatorial structures (in preparation). · Zbl 1200.05084 |
| [45] | Klin, M.C., Pöschel, R., Rosenbaum, K., 1988. Angewandte Algebra für Mathematiker und Informatiker. VEB Deutscher Verlag der Wissenschaften, Berlin, einführung in gruppentheoretisch-kombinatorische Methoden. [Introduction to group-theoretical combinatorial methods].; Klin, M.C., Pöschel, R., Rosenbaum, K., 1988. Angewandte Algebra für Mathematiker und Informatiker. VEB Deutscher Verlag der Wissenschaften, Berlin, einführung in gruppentheoretisch-kombinatorische Methoden. [Introduction to group-theoretical combinatorial methods]. · Zbl 0648.20001 |
| [46] | Klin, M.H., Lauri, J., Ziv-Av, M., 2011. Links between two semisymmetric graphs on 112 vertices through the lens of association schemes, preprint.; Klin, M.H., Lauri, J., Ziv-Av, M., 2011. Links between two semisymmetric graphs on 112 vertices through the lens of association schemes, preprint. · Zbl 1244.05235 |
| [47] | Lauri, J.; Mizzi, R.; Scapellato, R., Two-fold orbital digraphs and other constructions, Int. J. Pure Appl. Math. Sci., 1, 63-93 (2004) · Zbl 1079.05038 |
| [48] | Lauri, J.; Mizzi, R.; Scapellato, R., Two-fold automorphisms of graphs, Australas. J. Combin., 49, 165-176 (2011) · Zbl 1228.05164 |
| [49] | Lauri, J.; Scapellato, R., Topics in graph automorphisms and reconstruction, (London Mathematical Society Student Texts, vol. 54 (2003), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 1038.05025 |
| [50] | LJU, 2010. The ljubljana graph. URL: http://en.wikipedia.org/wiki/Ljubljana_graph; LJU, 2010. The ljubljana graph. URL: http://en.wikipedia.org/wiki/Ljubljana_graph |
| [51] | Marušič, D.; Pisanski, T., The Gray graph revisited, J. Graph Theory, 35, 1, 1-7 (2000), URL: http://dx.doi.org/10.1002/1097-0118(200009)35:1<1::AID-JGT1>3.0.CO;2-7 · Zbl 1021.05049 |
| [52] | Marušič, D.; Scapellato, R.; Zagaglia Salvi, N., A characterization of particular symmetric \((0, 1)\) matrices, Linear Algebra Appl., 119, 153-162 (1989), URL: http://dx.doi.org/10.1016/0024-3795(89)90075-X · Zbl 0677.15006 |
| [53] | McKay, B. D., Nauty User’s Guide (version 1.5) (1990) |
| [54] | Sharry, M. J.; Street, A. P., Partitioning sets of triples into designs, Ars Combin., 26, B, 51-66 (1988) · Zbl 0685.05006 |
| [55] | Sims, C. C., Computational methods in the study of permutation groups, (Computational Problems in Abstract Algebra, Proc. Conf., Oxford, 1967 (1970), Pergamon: Pergamon Oxford), 169-183 · Zbl 0215.10002 |
| [56] | Soicher, L. H., GRAPE: a system for computing with graphs and groups, (Groups and Computation, New Brunswick, NJ, 1991. Groups and Computation, New Brunswick, NJ, 1991, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 11 (1993), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 287-291 · Zbl 0833.05071 |
| [57] | Weisstein, E.W., 2010. Doyle graph. URL: http://mathworld.wolfram.com/DoyleGraph.html/; Weisstein, E.W., 2010. Doyle graph. URL: http://mathworld.wolfram.com/DoyleGraph.html/ |
| [58] | Wielandt, H., 1969. Permutation groups through invariant relations and invariant functions. Ohio State University, Columbus.; Wielandt, H., 1969. Permutation groups through invariant relations and invariant functions. Ohio State University, Columbus. |
| [59] | Zelinka, B., Isotopy of digraphs, Czechoslovak Math. J., 22, 97, 353-360 (1972) · Zbl 0239.05118 |
| [60] | Zelinka, B., On double covers of graphs, Math. Slovaca, 32, 1, 49-54 (1982) · Zbl 0483.05057 |
| [61] | Zelinka, B., Double covers and logics of graphs, Czechoslovak Math. J., 33(108), 3, 354-360 (1983) · Zbl 0537.05070 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
