Search

A graph is said to be distance-hereditary if the distance function in every connected induced subgraph is the same as in the graph itself. We prove that the ordinary Weisfeiler–Leman algorithm tests the isomorphism of any two graphs if one of them is distance-hereditary; more precisely, the Weisfeiler–Leman dimension of the class of finite distance-hereditary graphs is equal to 2. The previously best known upper bound for the dimension was 7. [ABSTRACT FROM AUTHOR]

It is well known that the automorphism group of a regular dessin is a two-generator finite group, and the isomorphism classes of regular dessins with automorphism groups isomorphic to a given finite group G are in one-to-one correspondence with the orbits of the action of Aut(G) on the ordered generating pairs of G. If there is only one orbit, then up to isomorphism the regular dessin is uniquely determined by the group G and it is called uniquely regular. In this paper we investigate the classification of uniquely regular dessins with a nilpotent automorphism group. The problem is reduced to the classification of finite maximally automorphic p-groups G, i.e., the order of the automorphism group of G attains Hall's upper bound. Maximally automorphic p-groups of nilpotency class three are classified. [ABSTRACT FROM AUTHOR]

Let G be a finite group having a factorisation G = AB into subgroups A and B with B cyclic and A∩B = 1, and let b be a generator of B. The associated skew-morphism is the bijective mapping f W A → A well-defined by the equality baB = f .a/B, where a ∊ A. In this paper, we shall classify all skew-morphisms of cyclic p-groups, where p is an odd prime. [ABSTRACT FROM AUTHOR]

In this paper we give a few discrete versions of Robert Accola's results on Riemann surfaces with automorphism groups admitting partitions. As a consequence, we establish a condition for $$\gamma $$ -hyperelliptic involution on a graph to be unique. Also we construct an infinite family of graphs with more than one $$\gamma $$ -hyperelliptic involution. [ABSTRACT FROM AUTHOR]

In this paper we generalise Singerman's results on triangle group inclusions to the broader class of generalised quadrangle groups, that is, Fuchsian groups with signature of genus 0 and generated by three or four elliptic generators. For any possible inclusion $$P

A 2-cell decomposition of a closed orientable surface is called a regular map if its automorphism group acts transitively on the set of all its darts (or arcs). It is well known that the group $$G = \mathrm{Aut}^+(\mathcal {M})$$ of all orientation-preserving automorphisms of such a map $$\mathcal {M}$$ is a finite quotient of the free product $$\Gamma = \mathbb {Z}* C_2$$ . In this paper we investigate the situation where G is nilpotent and the underlying graph of the map is simple (with no multiple edges). By applying a theorem of Labute (Proc Amer Math Soc 66:197-201, 1977) on the ranks of the factors of the lower central series of $$\Gamma $$ (via the associated Lie algebra), we prove that the number of vertices of any such map is bounded by a function of the nilpotency class of the group G. Moreover, we show that for a fixed nilpotency class c there is exactly one such simple regular map $$\mathcal {M}_c$$ attaining the bound, and that this map is universal, in the sense that every simple regular map $$\mathcal {M}$$ for which $$\mathrm{Aut}^+(\mathcal {M})$$ is nilpotent of class at most c is a quotient of $$\mathcal {M}_c$$ . In particular, there are finitely many such quotients for any given value of c, and every regular map $$\mathcal {M}$$ , whether simple or non-simple, for which $$\mathrm{Aut}^+(\mathcal {M})$$ is nilpotent of class at most c, is a cyclic cover of exactly one of them. [ABSTRACT FROM AUTHOR]

The aim of this paper is to find explicit formulae for the number of rooted hypermaps with a given number of darts on an orientable surface of genus $$g\le 3$$ . Such formulae were obtained earlier for $$g=0$$ and $$g=1$$ by Walsh and Arquès respectively. We first employ the Egorychev's method of counting combinatorial sums to obtain a new version of the Arquès formula for genus $$g=1$$ . Then we apply the same approach to get new results for genus $$g=2,3$$ . We could do it due to recent results by Giorgetti, Walsh, and Kazarian, Zograf who derived two different, but equivalent, forms of the generating functions for the number of hypermaps of genus two and three. [ABSTRACT FROM AUTHOR]

We prove the existence of infinitely many orientably-regular but chiral maps of every given hyperbolic type {m, k}, by constructing base examples from suitable permutation representations of the ordinary (2, k,m) triangle group, and then taking abelian p-covers. The base examples also help to prove that for every pair (k,m) of integers with 1/k + 1/m ⩽ 1/2, there exist infinitely many regular and infinitely many orientably-regular but chiral maps of type {m, k}, each with the property that both the map and its dual have simple underlying graph. [ABSTRACT FROM AUTHOR]

A dessin is an embedding of connected bipartite graph into an oriented closed surface. A dessin is regular if its group of colour- and orientation-preserving automorphisms acts transitively on the edges. In the present paper regular dessins with a nilpotent automorphism group are investigated, and attention are paid on those with the highest level of external symmetry. Depending on the algebraic theory of dessins and using group-theoretical methods, we present a classification of nilpotent groups of class two which underly a unique regular dessin. [ABSTRACT FROM AUTHOR]

We use the term half-regular map to describe an orientable map with an orientation preserving automorphism group that is transitive on vertices and half-transitive on darts. We present a full classification of half-regular Cayley maps using the concept of skew-morphisms. We argue that half-regular Cayley maps come in two types: those that arise from two skew-morphism orbits of equal size that are both closed under inverses and those that arise from two equal-sized orbits that do not contain involutions or inverses but one contains the inverses of the other. In addition, half-regular Cayley maps of the first type are shown to be half-edge-transitive, while half-regular Cayley maps of the second type are shown to be necessarily edge-transitive. A connection between half-regular Cayley maps and regular hypermaps is also investigated. [ABSTRACT FROM AUTHOR]

n orientably-regular map is a 2-cell embedding of a connected graph or multigraph into an orientable surface, such that the group of all orientation-preserving automorphisms of the embedding has a single orbit on the set of all arcs (incident vertex-edge pairs). Such embeddings of the n-dimensional cubes Q were classified for all odd n by Du, Kwak and Nedela in 2005, and in 2007, Jing Xu proved that for n=2 m where m is odd, they are precisely the embeddings constructed by Kwon in 2004. Here, we give a classification of orientably-regular embeddings of Q for all n. In particular, we show that for all even n (=2 m), these embeddings are in one-to-one correspondence with elements σ of order 1 or 2 in the symmetric group S such that σ fixes n, preserves the set of all pairs B={ i, i+ m} for 1≤ i≤ m, and induces the same permutation on this set as the permutation B ↦ B for some additive bijection f:ℤ→ℤ. We also give formulae for the numbers of embeddings that are reflexible and chiral, respectively, showing that the ratio of reflexible to chiral embeddings tends to zero for large even n. [ABSTRACT FROM AUTHOR]

A Cayley snark is a cubic Cayley graph which is not 3-edge-colourable. In the paper we discuss the problem of the existence of Cayley snarks. This problem is closely related to the problem of the existence of non-hamiltonian Cayley graphs and to the question whether every Cayley graph admits a nowhere-zero 4-flow. So far, no Cayley snarks have been found. On the other hand, we prove that the smallest example of a Cayley snark, if it exists, comes either from a non-abelian simple group or from a group which has a single non-trivial proper normal subgroup. The subgroup must have index two and must be either non-abelian simple or the direct product of two isomorphic non-abelian simple groups. [ABSTRACT FROM AUTHOR]