BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
The d-Simultaneous Conjugacy problem in the symmetric group Sn asks whether there exists a permutation τ∈Sn such that bj=τ−1ajτ holds for all j=1,2,…,d, where a1,a2,…,ad and b1,b2,…,bd are given sequences of permutations in Sn. The time complexity of existing algorithms for solving the problem is O(dn2). We show that for a given positive integer d the d-Simultaneous Conjugacy problem in Sn can be solved in o(n2) time.
A connected graph whose automorphism group acts transitively on the edges and vertices, but not on the set of ordered pairs of adjacent vertices of the graph is called half-arc-transitive. It is well known that the valence of a half-arc-transitive graph is even and at least four. Several infinite families of half-arc-transitive graphs of valence four are known, however, in all except four of the known specimens, the vertex-stabiliser in the automorphism group is abelian. The first example of a half-arc-transitive graph of valence four and with a non-abelian vertex-stabiliser was described in [Conder and Marušič, A tetravalent half-arc-transitive graph with non-abelian vertex stabilizer, J. Combin. Theory Ser. B 88 (2003) 67--76]. This example has 10752 vertices and vertex-stabiliser isomorphic to the dihedral group of order 8. In this paper, we show that no such graphs of smaller order exist, thus answering a frequently asked question.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.