Links between two semisymmetric graphs on 112 vertices via association schemes

摘要

This paper provides a model of the use of computer algebra experimentation in algebraic graph theory. Starting from the semisymmetric cubic graph ￡ on 112 vertices, we embed it into another semisymmetric graph N of valency 15 on the same vertex set. In order to consider systematically the links between ￡ and 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.