A generating theorem of simple even triangulations with a finitizable set of reductions

We shall determine exactly two $(P,Q)$-irreducible even triangulations of the projective plane. This result is a new generating theorem of even triangulations of the projective plane, that is, every even triangulation of the projective plane can be obtained from one of those two $(P,Q)$-irreducible even triangulations by a sequence of two expansions called a $P$-expansion and a $Q$-expansion, which were used in Batagelj (1984, 1989), Drapal and Lisonek (2010). Furthermore, we prove that for any closed surface $F^2$ there are finitely many $(P,Q)$-irreducible even triangulations of $F^2$.     

5-Chromatic even triangulations on surfaces

A triangulation is said to be even if each vertex has even degree. It is known that every even triangulation on any orientable surface with sufficiently large representativity is 4-colorable [J. Hutchinson, B. Richter, P. Seymour, Colouring Eulerian triangulations, J. Combin. Theory, Ser. B 84 (2002) 225-239], but all graphs on any surface with large representativity are 5-colorable [C. Thomassen, Five-coloring maps on surfaces, J. Combin Theory Ser. B 59 (1993) 89-105]. In this paper, we shall characterize 5-chromatic even triangulations with large representativity, which appear only on nonorientable surfaces.     

Generating even triangulations of the projective plane

We shall determine the 20 families of irreducible even triangulations of the projective plane. Every even triangulation of the projective plane can be obtained from one of them by a sequence of even‐splittings and attaching octahedra, both of which were first given by Batagelj 2 . © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 333–349, 2007     

Generating spherical Eulerian triangulations

We show that all spherical Eulerian triangulations can be inductively generated from the set of all even double wheels using just one of the two local transformations used in the algorithm by Brinkmann and McKay and originally proposed by Batagelj.     

N‐flips in even triangulations on the sphere

A triangulation is said to be even if each vertex has even degree. For even triangulations, define the N‐flip and the P2‐flip as two deformations preserving the number of vertices. We shall prove that any two even triangulations on the sphere with the same number of vertices can be transformed into each other by a sequence of N‐ and P2‐flips. © 2005 Wiley Periodicals, Inc. J. Graph Theory     

Spanning bipartite quadrangulations of even triangulations

A triangulation (resp., a quadrangulation) on a surface is a map of a loopless graph (possibly with multiple edges) on with each face bounded by a closed walk of length 3 (resp., 4). It is easy to see that every triangulation on any surface has a spanning quadrangulation. Kündgen and Thomassen proved that every even triangulation (ie, each vertex has even degree) on the torus has a spanning nonbipartite quadrangulation, and that if has sufficiently large edge width, then also has a bipartite one. In this paper, we prove that an even triangulation on the torus admits a spanning bipartite quadrangulation if and only if does not have as a subgraph, and moreover, we give some other results for the problem.     

Grünbaum colorings of even triangulations on surfaces

A Grünbaum coloring of a triangulation G is a map c : such that for each face f of G, the three edges of the boundary walk of f are colored by three distinct colors. By Four Color Theorem, it is known that every triangulation on the sphere has a Grünbaum coloring. So, in this article, we investigate the question whether each even (i.e., Eulerian) triangulation on a surface with representativity at least r has a Grünbaum coloring. We prove that, regardless of the representativity, every even triangulation on a surface has a Grünbaum coloring as long as is the projective plane, the torus, or the Klein bottle, and we observe that the same holds for any surface with sufficiently large representativity. On the other hand, we construct even triangulations with no Grünbaum coloring and representativity , and 3 for all but finitely many surfaces. In dual terms, our results imply that no snark admits an even map on the projective plane, the torus, or the Klein bottle, and that all but finitely many surfaces admit an even map of a snark with representativity at least 3.     

Polychromatic 4-coloring of cubic even embeddings on the projective plane

A polychromatic     k$k$-coloring   of a map G$G$ on a surface is a k$k$-coloring such that each face of G$G$ has all k$k$ colors on its boundary vertices. An even embedding     G$G$ on a surface is a map of a simple graph on the surface such that each face of G$G$ is bounded by a cycle of even length. In this paper, we shall prove that a cubic even embedding G$G$ on the projective plane has a polychromatic proper 4-coloring if and only if G$G$ is not isomorphic to a Möbius ladder with an odd number of rungs. For proving the theorem, we establish a generating theorem for 3-connected Eulerian multi-triangulations on the projective plane.     

Irreducible triangulations of the torus

By Steinitz' Theorem all triangulations of a sphere are generated from one triangulation with four vertices by certain sequences of operations called vertex splittings. A theorem of Barnette asserts that all triangulations of the projective plane can be generated from two irreducible triangulations. In the present work we obtain an analogous result for the torus: we show that all triangulations of the torus are generated by 21 irreducible triangulations (they are found explicitly) by applying the same vertex splitting operations. Two tables, one figure.Translated from Ukrainskií Geometricheskií Sbornik, No. 30, 1987, pp. 52–62.     

N-Flips in even triangulations on surfaces

In this paper, we show that any two even triangulations on the same closed surface with the same and sufficiently large number of vertices can be transformed into each other by a sequence of two specifically defined deformations called an N-flip and a $P_2$-flip, up to homeomorphism, if they have the same homological structure.     

Generating functions via integral transforms

In this paper, we use some integral transforms to derive, for a polynomial sequence {Pn(x)}_n?0, generating functions of the type , starting from a generating function of type , where {γn}_n?0 is a real numbers sequence independent on x and t. That allows us to unify the treatment of a generating function problem for many well-known polynomial sequences in the literature.     

Conforming Delaunay triangulations in 3D

We describe an algorithm which, for any piecewise linear complex (PLC) in 3D, builds a Delaunay triangulation conforming to this PLC. The algorithm has been implemented, and yields in practice a relatively small number of Steiner points due to the fact that it adapts to the local geometry of the PLC. It is, to our knowledge, the first practical algorithm devoted to this problem.     

A characterization of even doubly-stochastic matrices

Even doubly-stochastic matrices are characterized with the aid of the minima of functionals defined by the even diagonals contained in the matrix.     

Geodesic ideal triangulations exist virtually

It is shown that every non-compact hyperbolic manifold of finite volume has a finite cover admitting a geodesic ideal triangulation. Also, every hyperbolic manifold of finite volume with non-empty, totally geodesic boundary has a finite regular cover which has a geodesic partially truncated triangulation. The proofs use an extension of a result due to Long and Niblo concerning the separability of peripheral subgroups.

     

Khovanov homology of torus links

In this paper we show that there is a cut-off in the Khovanov homology of (2k,2kn)-torus links, namely that the maximal homological degree of non-zero homology groups of (2k,2kn)-torus links is 2k²n. Furthermore, we calculate explicitly the homology group in homological degree 2k²n and prove that it coincides with the center of the ring Hk of crossingless matchings, introduced by M. Khovanov in [M. Khovanov, A functor-valued invariant for tangles, Algebr. Geom. Topol. 2 (2002) 665-741, arXiv:math.QA/0103190]. This gives the proof of part of a conjecture by M. Khovanov and L. Rozansky in [M. Khovanov, L. Rozansky, A homology theory for links in S²×S¹, in preparation]. Also we give an explicit formula for the ranks of the homology groups of (3,n)-torus knots for every n∈N.     

A note on the weakly convex and convex domination numbers of a torus

The distanced_G(u,v) between two vertices u and v in a connected graph G is the length of the shortest (u,v) path in G. A (u,v) path of length d_G(u,v) is called a (u,v)-geodesic. A set X⊆V is called weakly convex in G if for every two vertices a,b∈X, exists an (a,b)-geodesic, all of whose vertices belong to X. A set X is convex in G if for all a,b∈X all vertices from every (a,b)-geodesic belong to X. The weakly convex domination number of a graph G is the minimum cardinality of a weakly convex dominating set of G, while the convex domination number of a graph G is the minimum cardinality of a convex dominating set of G. In this paper we consider weakly convex and convex domination numbers of tori.