Uniquely and faithfully embeddable projective-planar triangulations

Let G be a 5-connected graph not isomorphic to the complete graph K₆ with 6 vertices and triangularly embedded in a projective plane P². Then it will be shown that for any embedding f: G → P², there is a homeomorphism h: P² → P² such that h| G = f. In our terminology, the result states that every 5-connected projective-planar triangulation is uniquely and faithfully embeddable in a projective plane unless it is isomorphic to K₆.     

Prism‐hamiltonicity of triangulations

The prism over a graph G is the Cartesian product G □ K₂ of G with the complete graph K₂. If the prism over G is hamiltonian, we say that G is prism‐hamiltonian. We prove that triangulations of the plane, projective plane, torus, and Klein bottle are prism‐hamiltonian. We additionally show that every 4‐connected triangulation of a surface with sufficiently large representativity is prism‐hamiltonian, and that every 3‐connected planar bipartite graph is prism‐hamiltonian. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 181–197, 2008     

Chromatic numbers of quadrangulations on closed surfaces

It has been shown that every quadrangulation on any nonspherical orientable closed surface with a sufficiently large representativity has chromatic number at most 3. In this paper, we show that a quadrangulation G on a nonorientable closed surface N_k has chromatic number at least 4 if G has a cycle of odd length which cuts open N_k into an orientable surface. Moreover, we characterize the quadrangulations on the torus and the Klein bottle with chromatic number exactly 3. By our characterization, we prove that every quadrangulation on the torus with representativity at least 9 has chromatic number at most 3, and that a quadrangulation on the Klein bottle with representativity at least 7 has chromatic number at most 3 if a cycle cutting open the Klein bottle into an annulus has even length. As an application of our theory, we prove that every nonorientable closed surface N_k admits an eulerian triangulation with chromatic number at least 5 which has arbitrarily large representativity. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 100–114, 2001     

Block designs and graph imbeddings

Heffter first observed that certain imbeddings of complete graphs give rise to BIBD's with k = 3 and λ = 2 (and sometimes λ = 1); Alpert established a one-to-one correspondence between BIBD's with k = 3 and λ = 2 and triangulation systems for complete graphs. In this paper we extend this correspondence to PBIBD's on two association classes with k = 3, λ₁ = 0 and λ₂ = 2, and triangulation systems for strongly regular graphs. The group divisible designs of Hanani are used to construct triangulations for the graphs K_n(m), in each case permitted by the euler formula. Conversely, triangular imbeddings of K_n(m) are constructed which lead to new group divisible designs. A process is developed for “doubling” a given PBIBD of an appropriate form. Various extensions of these ideas are discussed, as is an application to the construction of quasigroups.     

Quadratic forms over polynomial rings over global fields

It is proved that a quadratic space over the polynomial extension of a global field K is extended from K if it is extended from K_v for every completion K_v of K.     

Minimal non-1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge. A non-1-planar graph G is minimal if the graph G-e is 1-planar for every edge e of G. We prove that there are infinitely many minimal non-1-planar graphs (MN-graphs). It is known that every 6-vertex graph is 1-planar. We show that the graph K₇-K₃ is the unique 7-vertex MN-graph.     

Properly coloured Hamiltonian cycles in edge-coloured complete graphs

Let K ^c _n be an edge-coloured complete graph on n vertices. Let Δ_mon(K^c _n) denote the largest number of edges of the same colour incident with a vertex of K^c _n. A properly coloured cycleis a cycle such that no two adjacent edges have the same colour. In 1976, BollobÁs and Erd?s[6] conjectured that every K^c _n with Δ_mon(K^c _n)<?n/2?contains a properly coloured Hamiltonian cycle. In this paper, we show that for any ε>0, there exists an integer n₀ such that every K^c _n with Δ_mon(K^c _n)<(1/2–ε)n and n≥n₀ contains a properly coloured Hamiltonian cycle. This improves a result of Alon and Gutin [1]. Hence, the conjecture of BollobÁs and Erd?s is true asymptotically.     

Minimal 2-matching-covered graphs

A perfect 2-matching M of a graph G is a spanning subgraph of G such that each component of M is either an edge or a cycle. A graph G is said to be 2-matching-covered if every edge of G lies in some perfect 2-matching of G. A 2-matching-covered graph is equivalent to a “regularizable” graph, which was introduced and studied by Berge. A Tutte-type characterization for 2-matching-covered graph was given by Berge. A 2-matching-covered graph is minimal if G−e is not 2-matching-covered for all edges e of G. We use Berge’s theorem to prove that the minimum degree of a minimal 2-matching-covered graph other than K₂ and K₄ is 2 and to prove that a minimal 2-matching-covered graph other than K₄ cannot contain a complete subgraph with at least 4 vertices.     

Universal meromorphic approximation on Vitushkin sets

The paper proves the following result on universal meromorphic approximation: Given any unbounded sequence {λ _n } ? ?, there exists a function ?, meromorphic on ?, with the following property. For every compact set K of rational approximation (i.e. Vitushkin set), and every function f, continuous on K and holomorphic in the interior of K, there exists a subsequence {n _k } of ? such that $ \left\{ {\varphi \left( {z + \lambda _{n_k } } \right)} \right\} The paper proves the following result on universal meromorphic approximation: Given any unbounded sequence {λ _n } ⊂ ℂ, there exists a function ϕ, meromorphic on ℂ, with the following property. For every compact set K of rational approximation (i.e. Vitushkin set), and every function f, continuous on K and holomorphic in the interior of K, there exists a subsequence {n _k } of ℕ such that converges to f(z) uniformly on K. A similar result is obtained for arbitrary domains G ≠ ℂ. Moreover, in case {λ _n }={n} the function ϕ is frequently universal in terms of Bayart/Grivaux [3]. Original Russian Text ? W.Luh, T.Meyrath, M.Niess, 2008, published in Izvestiya NAN Armenii. Matematika, 2008, No. 6, pp. 66–75.     

Del Pezzo surfaces of degree 6 over an arbitrary field

We give a characterization of all del Pezzo surfaces of degree 6 over an arbitrary field F. A surface is determined by a pair of separable algebras. These algebras are used to compute the Quillen K-theory of the surface. As a consequence, we obtain an index reduction formula for the function field of the surface.     

Subgraphs in vertex neighborhoods of Kr‐free graphs

In a K_r‐free graph, the neighborhood of every vertex induces a K_{r ? 1}‐free subgraph. The K_r‐free graphs with the converse property that every induced K_{r ? 1}‐free subgraph is contained in the neighborhood of a vertex are characterized, based on the characterization in the case r ? 3 due to Pach [ 8 ]. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 29–38, 2004     

The graphs with only self-dual signings

Given a graph G, it is possible to attach positive and negative signs to its lines only, to its points only, or to both. The resulting structures are called respectively signed graphs, marked graphs and nets. The dual of each such structure is obtained by changing every sign in it. We determine all graphs G for which every suitable marked graph on G is self-dual (the M-dual graphs), and also the corresponding graphs G for signed graphs (S-dual) and for nets (N-dual.A graph G is M-dual if and only if G or ? is one of the graphs K_2m, 2K_m, mK₂, K_m + K₂ or 2C₄. The S-dual graphs are C₆, 2C₃, 2C₄, 2K_1n, 2nK₂, K_1,2n, nK_1,2, K_2n, K?_n and all graphs obtained from these by the addition of isolated points. Finally, the only N-dual graph other than -K_2n is 2K₂.     

When is c(x) a Clean Ring?

An element of a ring R is called clean if it is the sum of a unit and an idempotent and a subset A of R is called clean if every element of A is clean. A topological characterization of clean elements of C(X) is given and it is shown that C(X) is clean if and only if X is strongly zero-dimensional, if and only if there exists a clean prime ideal in C(X). We will also characterize topological spaces X for which the ideal C_K(X) is clean. Whenever X is locally compact, it is shown that C_K(X) is clean if and only if X is zero-dimensional.     

On maximal convex lattice polygons inscribed in a plane convex set

Given a convex compact setK ? ?₂ what is the largestn such thatK contains a convex latticen-gon? We answer this question asymptotically. It turns out that the maximaln is related to the largest affine perimeter that a convex set contained inK can have. This, in turn, gives a new characterization ofK ₀, the convex set inK having maximal affine perimeter.     

On the number of Hamiltonian cycles in triangulations

It is proved that if a planar triangulation different from K₃ and K₄ contains a Hamiltonian cycle, then it contains at least four of them. Together with the result of Hakimi, Schmeichel, and Thomassen [2], this yields that, for n ? 12, the minimum number of Hamiltonian cycles in a Hamiltonian planar triangulation on n vertices is four. We also show that this theorem holds for triangulations of arbitrary surfaces and for 3-connected triangulated graphs.     

Diamond-free circle graphs are Helly circle

The diamond is the graph obtained from K₄ by deleting an edge. Circle graphs are the intersection graphs of chords in a circle. Such a circle model has the Helly property if every three pairwise intersecting chords intersect in a single point, and a graph is Helly circle if it has a circle model with the Helly property. We show that the Helly circle graphs are the diamond-free circle graphs, as conjectured by Durán. This characterization gives an efficient recognition algorithm for Helly circle graphs.     

K6‐minors in triangulations and complete quadrangulations

In this paper, we shall prove that a projective‐planar (resp., toroidal) triangulation G has K₆ as a minor if and only if G has no quadrangulation isomorphic to K₄ (resp., K₅ ) as a subgraph. As an application of the theorems, we can prove that Hadwiger's conjecture is true for projective‐planar and toroidal triangulations. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 302‐312, 2009     

Linearly ordered compacta and Banach spaces with a projectional resolution of the identity

We construct a compact linearly ordered space Kω₁ of weight ℵ₁, such that the space C(Kω₁) is not isomorphic to a Banach space with a projectional resolution of the identity, while on the other hand, Kω₁ is a continuous image of a Valdivia compact and every separable subspace of C(Kω₁) is contained in a 1-complemented separable subspace. This answers two questions due to O. Kalenda and V. Montesinos.     

On a problem of G. Hahn about coloured hamiltonian paths in K2t

We prove a theorem showing that for every integer p (p?2) there is a good minimal coloring of the edges of K_2^p such that every hamiltonian path in K_2^p uses at least one colour twice. This gives a counter-example to a conjecture of Hahn [2].