Classification of Regular Embeddings of Complete Multipartite Graphs

A 2‐cell embedding of a graph Γ into a closed (orientable or nonorientable) surface is called regular if its automorphism group acts regularly on the flags. In this article, we classify the regular embeddings of the complete multipartite graph $K_{n,\dots ,n}$. We show that if the number of partite sets is greater than 3, there exists no such embedding; and if the number of partite sets is 3, for any n, there exist one orientable regular embedding and one nonorientable regular embedding of $K_{n,n,n}$ up to isomorphism.     

Nowhere-zero flows in low genus graphs

A nowhere-zero k-flow is an assignment of edge directions and integer weights in the range 1,…, k ? 1 to the edges of an undirected graph such that at every vertex the flow in is equal to the flow out. Tutte has conjectured that every bridgeless graph has a nowhere-zero 5-flow. We show that a counterexample to this conjecture, minimal in the class of graphs embedded in a surface of fixed genus, has no face-boundary of length <7. Moreover, in order to prove or disprove Tutte's conjecture for graphs of fixed genus γ, one has to check graphs of order at most 28(γ ? 1) in the orientable case and 14(γ ? 2) in the nonorientable case. So, in particular, it follows immediately that every bridgeless graph of orientable genus ?1 or nonorientable genus ?2 has a nowhere-zero 5-flow. Using a computer, we checked that all graphs of orientable genus ?2 or nonorientable genus ?4 have a nowhere-zero 5-flow.     

在不可定向的流形网格曲面上计算测地距离的一般方法

不可定向的流形曲面不仅在拓扑学中占据重要的地位,在可视化和极小曲面等问题中也有很多的应用.从拓扑学的观点来看,二流形曲面的每个局部与圆盘同胚,该性质与曲面的全局可定向性无关.但在离散化的网格表示上,可定向的二流形曲面常用半边结构来表达,而不可定向的二流形曲面大多表达成若干多边形的集合,这给以可定向网格曲面为主要研究对象的数字几何处理带来很多不便.本文提出了把不可定向的二流形网格曲面上的测地距离问题转化到可定向曲面上进行处理的一般算法框架.该框架有望在不可定向的二流形网格曲面与传统数字几何处理方法之间搭起一座桥梁.为了展示该算法框架的普适性,本文将其应用于不可定向曲面上的三个重要场合,包括测地距离的求解、离散指数映射和最远点采样.     

Orientation-reversing free actions on handlebodies

We examine free orientation-reversing group actions on orientable handlebodies, and free actions on nonorientable handlebodies. A classification theorem is obtained, giving the equivalence classes and weak equivalence classes of free actions in terms of algebraic invariants that involve Nielsen equivalence. This is applied to describe the sets of free actions in various cases, including a complete classification for many (and conjecturally all) cases above the minimum genus. For abelian groups, the free actions are classified for all genera.     

An Euler‐genus approach to the calculation of the crosscap‐number polynomial

In 1994, J. Chen, J. Gross, and R. Rieper demonstrated how to use the rank of Mohar's overlap matrix to calculate the crosscap‐number distribution, that is, the distribution of the embeddings of a graph in the nonorientable surfaces. That has ever since been by far the most frequent way that these distributions have been calculated. This article introduces a way to calculate the Euler‐genus polynomial of a graph, which combines the orientable and the nonorientable embeddings, without using the overlap matrix. The crosscap‐number polynomial for the nonorientable embeddings is then easily calculated from the Euler‐genus polynomial and the genus polynomial.     

Classification of regular embeddings of hypercubes of odd dimension

By a regular embedding of a graph into a closed surface we mean a 2-cell embedding with the automorphism group acting regularly on flags. Recently, Kwon and Nedela [Non-existence of nonorientable regular embeddings of n-dimensional cubes, Discrete Math., to appear] showed that no regular embeddings of the n-dimensional cubes Q_n into nonorientable surfaces exist for any positive integer n>2. In 1997, Nedela and Škoviera [Regular maps from voltage assignments and exponent groups, European J. Combin. 18 (1997) 807-823] presented a construction giving for each solution of the congruence a regular embedding M_e of the hypercube Q_n into an orientable surface. It was conjectured that all regular embeddings of Q_n into orientable surfaces can be constructed in this way. This paper gives a classification of regular embeddings of hypercubes Q_n into orientable surfaces for n odd, proving affirmatively the conjecture of Nedela and Škoviera for every odd n.     

Nonorientable genus of cartesian products of regular graphs

A special type of surgery developed by A. T. White and later used by the author to construct orientable quadrilateral embeddings of Cartesian products of graphs is here expanded to cover the nonorientable case as well. This enables the nonorientable genus of many families of Cartesian products of triangle-free graphs to be computed.     

Voltage graph embeddings and the associated block designs

The voltage graph construction of Gross (orientable case) and Stahl as well as Gross and Tucker (nonorientable case) is extended to the case where the base graph is embedded in a pseudosurface or a generalized pseudosurface. This theory is then applied to produce triangular embeddings of K_4(n); they in turn yield an infinite class of partially balanced incomplete block designs.     

循环图C(n,m)}的最小亏格

本文给出了所有循环图的可定向与不可定向最小亏格. 同时, 也给出了部分循环图的强最小亏格.     

THE TOPOLOGICAL AND DYNAMICAL PROPERTIES OF NONORIENTABLE SURFACES

Four topological and dynamical properties of nonorientable surfaces are proved.Thefirst is that for every continuous flow defined on any nonorientable closed surface,thereexist periodic or singular closed orbits.In the case of the projective plane,it confirms aconjecture of professor Ye Yian-qian in his lecture notes“dynamical systems on surfaces”.Secondly,the author gives an exact upper bound of the number of closed curves onnonorientable surfaces,which do not intersect each other and the complement of their sumis still connected.The third is concerned with the upper and lower bound of the number ofthe periodic or singular closed orbits with certain properties.The last is related to theconnectedness of the complement of a lifting curve on two-fold covering space.The firstproperty may be considered as a generalization of Kneser theorem from Klein bottle togeneral nonorientable surfaces and the second as a generalization of[4]Theorem 9.3.6from orientable surfaces to nonorientable surfaces.     

A census of petal bundles by genus

This paper provides the uniform enumerative functional equation of orientable （nonori-entable） rooted petal bundles with more parameters, and deduces two recursion formulas for calculation. Accordingly, an explicit expression of rooted petal bundles with up to two parameters on nonorientable surface of genus 4 is also obtained.     

On large orientation-reversing finite group-actions on 3-manifolds and equivariant Heegaard decompositions

We consider finite group-actions on closed, orientable and nonorientable 3-manifolds; such a finite group-action leaves invariant the two handlebodies of a Heegaard splitting of M of some genus g. The maximal possible order of a finite group-action of an orientable or nonorientable handlebody of genus $$g>1$$ is $$24(g-1)$$, and in the present paper we characterize the 3-manifolds M and groups G for which the maximal possible order $$|G| = 24(g-1)$$ is obtained, for some G-invariant Heegaard splitting of genus $$g>1$$. If M is reducible then it is obtained by doubling an action of maximal possible order $$24(g-1)$$ on a handlebody of genus g. If M is irreducible then it is a spherical, Euclidean or hyperbolic manifold obtained as a quotient of one of the three geometries by a normal subgroup of finite index of a Coxeter group associated to a Coxeter tetrahedron, or of a twisted version of such a Coxeter group.     

On the minimal genus of 2-complexes

Gross and Rosen asked if the genus of a 2-dimensional complex K embeddable in some (orientable) surface is equal to the genus of the graph of appropriate barycentric subdivision of K. We answer the nonorientable genus and the Euler genus versions of Gross and Rosen's question in affirmative. We show that this is not the case for the orientable genus by proving that taking ⌊ log₂ g⌋ th barycentric subdivision is not sufficient, where g is the genus of K. On the other hand, (1+⌈log₂(g+2)⌉)th subdivision is proved to be sufficient. © 1997 John Wiley & Sons, Inc.     

Normal numbers of piecewise-linear manifolds

A definition is given of the normal class of the immersion of a closed piecewise-linear manifold in a piecewise-linear manifold. It is shown that this number is zero for the immersion of an orientable manifold in euclidean space of any dimension. A complete investigation is carried out of normal classes of piecewise-smooth immersions of nonorientable manifolds in a euclidean space with dimension twice that of the manifolds.Translated from Matematicheskie Zametki, Vol. 9, No. 5, pp. 575–583, May, 1971.     

Upper embedability of graphs

A connected loopless graph that can be embedded on some (orientable or nonorientable) surface such that the size of each face does not exceed 5 is upper embeddable.     

No optimal 1‐planar graph triangulates any nonorientable closed surface

Suzuki [Discrete Math. 310 (2010), 6–11] proved that for any orientable closed surface F² other than the sphere, there exists an optimal 1‐planar graph which can be embedded on F² as a triangulation. However, for nonorientable closed surfaces, the existence of such graphs is unknown. In this article, we prove that no optimal 1‐planar graph triangulates a nonorientable closed surface.     

An analogue of the Harer-Zagier formula for unicellular maps on general surfaces

A unicellular map is the embedding of a connected graph in a surface in such a way that the complement of the graph is simply connected. In a famous article, Harer and Zagier established a formula for the generating function of unicellular maps counted according to the number of vertices and edges. The keystone of their approach is a counting formula for unicellular maps on orientable surfaces with n edges, and with vertices colored using every color in [q] (adjacent vertices are authorized to have the same color). We give an analogue of this formula for general (locally orientable) surfaces.Our approach is bijective and is inspired by Lass?s proof of the Harer-Zagier formula. We first revisit Lass?s proof and twist it into a bijection between unicellular maps on orientable surfaces with vertices colored using every color in [q], and maps with vertex set [q] on orientable surfaces with a marked spanning tree. The bijection immediately implies Harer-Zagier?s formula and a formula by Jackson concerning bipartite unicellular maps. It also shed a new light on constructions by Goulden and Nica, Schaeffer and Vassilieva, and Morales and Vassilieva. We then extend the bijection to general surfaces and obtain a correspondence between unicellular maps on general surfaces with vertices colored using every color in [q], and maps on orientable surfaces with vertex set [q]with a marked planar submap. This correspondence gives an analogue of the Harer-Zagier formula for general surfaces. We also show that this formula implies a recursion formula due to Ledoux for the numbers of unicellular maps with given numbers of vertices and edges.     

Optimal 1-planar graphs which triangulate other surfaces

We show that, for any given non-spherical orientable closed surface F², there exists an optimal 1-planar graph which can be embedded on F² as a triangulation. On the other hand, we prove that there does not exist any such graph for the nonorientable closed surfaces of genus at most 3.     

A sequence representation for maps

An easy implementable polynomial algorithm to test for isomorphism of graphs embedded in arbitrary compact surfaces (maps) is given.

The map are defined algebraically by Tutte's axtom system. We produce a canonical codification of them as a sequence of 4e integers (2e if the map is orientable) where e is the number of edges. To test for isomorphism between two maps we just have to compare their codes.

Some applications relying on the implementation are given.     

Maximum genus embeddings of Steiner triple systems

We prove that for n>3 every STS(n) has both an orientable and a nonorientable embedding in which the triples of the STS(n) appear as triangular faces and there is just one additional large face. We also obtain detailed results about the possible automorphisms of such embeddings.