The Hamiltonian cycle problem is an important problem in graph theory and computer science. It is a special case of the famous traveling salesman problem. A signicant amount of research has been done on the special cases of nding Hamiltonian cycles in subgraphs of triangular, square and hexagonal grids. However, there is little work on more complicated grids. In this paper, we investigate the hardness of Hamiltonian cycle problem in grid graphs of semiregular tessellations, which are tessellations formed by two or more kinds of regular polygons. There are only eight semiregular tessellations, and we prove that the Hamiltonian cycle problem in all of them are NP-complete by reducing from NP-complete problems, such as the Hamiltonian cycle problem in max degree 3 bipartite planar graphs. Knowing the NP-completeness of Hamiltonian cycle problem in semiregular grids indicates that there will not be any polynomial time algorithm that solves the Hamiltonian path problem in these tessellations if NP does not equal to P, which helps show the limits of ecient motion planning algorithms and provides new information about what makes problems computationally dicult to solve.

Let $f(n)$ be the maximum number of edges in a graph on $n$ vertices in which no two cycles have the same length. In 1975, Erdos raised the problem of determining $f(n)$ (see J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, New York, 1976), p.247, Problem 11). Given a graph $H$, what is the maximum number of edges of a graph with $n$ vertices not containing $H$ as a subgraph? This number is denoted $ex(n,H)$, and is known as the Turan number. Erdos conjectured that there exists a positive constant $c$ such that $ex(n,C_{2k})\geq cn^{1+1/k}$(see P. Erdos, Some unsolved problems in graph theory and combinatorial analysis, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) , pp. 97--109, Academic Press, London, 1971). Haj\'{o}s conjectured that every simple even graph on $n$ vertices can be decomposed into at most $n/2$ cycles (see L. Lovasz, On covering of graphs, in: P. Erdos, G.O.H. Katona (Eds.), Theory of Graphs, Academic Press, New York, 1968, pp. 231 - 236 ). We present the problems, conjectures related to these problems and we summarize the know results.

Let M and N be two compact complex manifolds. We show that if the tautological line bundle O_{T^∗}M(1) is not pseudo-effective and O_{T^∗}N(1) is nef, then there is no non-constant holomorphic map from M to N. In particular, we prove that any holomorphic map from a compact complex manifold M with RC-positive tangent bundle to a compact complex manifold N with nef cotangent bundle must be a constant map. As an application, we obtain that there is no non-constant holomorphic map from a compact Hermitian manifold with positive holomorphic sectional curvature to a Hermitian manifold with non-positive holomorphic bisectional curvature.

In this article, a classification of continuous, linearly intertwining, symmetric $L_p$-Blaschke ($p>1$) valuations is established as an extension of Haberl's work on Blaschke valuations. More precisely, we show that for dimensions $n \geq 3$, the only continuous, linearly intertwining, normalized symmetric $L_p$-Blaschke valuation is the normalized $L_p$-curvature image operator, while for dimension $n = 2 $, a rotated normalized $L_p$-curvature image operator is an only additional one. One of the advantages of our approach is that we deal with normalized symmetric $L_p$-Blaschke valuations, which makes it possible to handle the case $p=n$. The cases where $p \neq =n$ are also discussed by studying the relations between symmetric $L_p$-Blaschke valuations and normalized ones.

No abstract uploaded!