On Finite Saturated Chains of Overrings

If a domain R, with quotient field K, has a finite saturated chain of overrings from R to K, then the integral closure of R is a Prüfer domain. An integrally closed domain R with quotient field K has a finite saturated chain of overrings from R to K with length m ≥ 1 iff R is a Prüfer domain and |Spec(R)| =m + 1. In particular, we prove that a domain R has a finite saturated chain of overrings from R to K with length dim(R) iff R is a valuation domain and that an integrally closed domain R has a finite saturated chain of overrings from R to K with length dim (R) +1 iff R is a Prüfer domain with exactly two maximal ideals such that at most one of them fails to contain every non-maximal prime. The relationship with maximal non-valuation subrings is also established.     

On complex manifolds polarized by an ample line bundle of sectional genus q ( X ) + 2

Let (X,L) be a polarized manifold with dim X = n. In this paper, we classify (X,L) with n = 3, , and g(L)=q(X) + 2. Moreover we also classify (X,L) with , g(L)=q(x) + 2, and . Received February 12, 1999     

Generalized projection and approximation of fixed points of nonself maps

Let K be a nonempty closed convex proper subset of a real uniformly convex and uniformly smooth Banach space E; T:K→E be an asymptotically weakly suppressive, asymptotically weakly contractive or asymptotically nonextensive map with F(T){xK: Tx=x}≠. Using the notion of generalized projection, iterative methods for approximating fixed points of T are studied. Convergence theorems with estimates of convergence rates are proved. Furthermore, the stability of the methods with respect to perturbations of the operators and with respect to perturbations of the constraint sets are also established.     

Proximal Set-Open Topologies on Partial Maps

Let X, Y be T ₁ topological spaces. A partial map from X to Y is a continuous function f whose domain is a subspace D of X and whose codomain is Y. Let P(X, Y) be the set of partial maps with domains in a fixed class D. In analogy with the global case, we introduce on P(X, Y), whatever be the nature of the domain class D, new function space topologies, the proximal set-open topologies, briefly PSOTs, deriving from general networks on X and proximity on Y by replacing inclusion with strong inclusion. The PSOTs include the already known generalized compact-open topology on partial maps with closed domains. When domains are supposed closed, the network α closed and hereditarily closed and the proximity δ on Y Efremovic, then the PSOT attached to α and δ is uniformizable iff α is a Urysohn family in X. This revised version was published online in June 2006 with corrections to the Cover Date.     

Hamiltonian properties of the cube of a 2-edge connected graph

Let G be a 2-edge connected graph with at least 5 vertices. For any given vertices a, b, c, and d in G with a ≠ b, there exists in G₃ a hamiltonian path with endpoints a and b avoiding the edge cd, and there exists in G₃ ∪ {cd} a hamiltonian path with endpoints a and b and containing the edge cd. Also, after removal of two edges or one edge and one vertex from G₃, the resulting graph is still hamiltonian.     

Reconstructible and Half-Reconstructible Tournaments: Application to Their Groups of Hemimorphisms

Let T and T¹ be tournaments with n elements, E a basis for T, E′ a basis for T′, and k ≥ 3 an integer. The dual of T is the tournament T” of basis E defined by T(x, y) = T(y, x) for all x, y ε E. A hemimorphism from T onto T′ is an isomorphism from T onto T” or onto T. A k-hemimorphism from T onto T′ is a bijection f from E to E′ such that for any subset X of E of order k the restrictions T/X and T¹/f(X) are hemimorphic. The set of hemimorphisms of T onto itself has group structure, this group is called the group of hemimorphisms of T. In this work, we study the restrictions to n – 2 elements of a tournament with n elements. In particular, we prove: Let k ≥ 3 be an integer, T a tournament with n elements, where n ≥ k + 5. Then the following statements are equivalent: (i) All restrictions of T to subsets with n – 2 elements are k-hemimorphic. (ii) All restrictions of T to subsets with n – 2 elements are 3-hemimorphic. (iii) All restrictions of T to subsets with n – 2 elements are hemimorphic. (iv) All restrictions of T to subsets with n – 2 elements are isomorphic, (v) Either T is a strict total order, or the group of hemimorphisms of T is 2-homogeneous.     

Non-existence of KAM torus

Given an integrable Hamiltonian h ₀ with n-degrees of freedom and a Diophantine frequency ω, then, arbitrarily close to h ₀ in the C ^r topology with r < 2n, there exists an analytical Hamiltonian h _ε with no KAM torus of rotation vector ω. In contrast with it, KAM tori exist if perturbations are small in C ^r topology with r > 2n.     

On the Existence of Solutions for Fully Nonlinear Elliptic Equations Under Relaxed Convexity Assumptions

We establish the existence and uniqueness of solutions of fully nonlinear elliptic second-order equations like H(v, Dv, D ² v, x) = 0 in smooth domains without requiring H to be convex or concave with respect to the second-order derivatives. Apart from ellipticity nothing is required of H at points at which |D ² v| ≤K, where K is any given constant. For large |D ² v| some kind of relaxed convexity assumption with respect to D ² v mixed with a VMO condition with respect to x are still imposed. The solutions are sought in Sobolev classes.     

On the Maximum Number of Cliques in a Graph

A clique is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with n vertices and m edges; (2) graphs with n vertices, m edges, and maximum degree Δ; (3) d-degenerate graphs with n vertices and m edges; (4) planar graphs with n vertices and m edges; and (5) graphs with n vertices and no K₅-minor or no K_3,3-minor. For example, the maximum number of cliques in a planar graph with n vertices is 8(n − 2). Research supported by a Marie Curie Fellowship of the European Community under contract 023865, and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224.     

Decomposing Hypergraphs into Simple Hypertrees

T be a simple k-uniform hypertree with t edges. It is shown that if H is any k-uniform hypergraph with n vertices and with minimum degree at least , and the number of edges of H is a multiple of t then H has a T-decomposition. This result is asymptotically best possible for all simple hypertrees with at least two edges. Received December 28, 1998     

A class of dimension-skipping graphs

Forn≧6 there exists a graphG with dimG=n, dimG*≧n+2, whereG* isG with a certain edge added.     

2‐connected 7‐coverings of 3‐connected graphs on surfaces

An m‐covering of a graph G is a spanning subgraph of G with maximum degree at most m. In this paper, we shall show that every 3‐connected graph on a surface with Euler genus k ≥ 2 with sufficiently large representativity has a 2‐connected 7‐covering with at most 6k ? 12 vertices of degree 7. We also construct, for every surface F² with Euler genus k ≥ 2, a 3‐connected graph G on F² with arbitrarily large representativity each of whose 2‐connected 7‐coverings contains at least 6k ? 12 vertices of degree 7. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 26–36, 2003     

Bicolored Matchings in Some Classes of Graphs

We consider the problem of finding in a graph a set R of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with n nodes on each side, we give sufficient conditions for the existence of a set R with |R|=n+1 such that perfect matchings with k red edges exist for all k,0≤k≤n. Given two integers p<q we also determine the minimum cardinality of a set R of red edges such that there are perfect matchings with p red edges and with q red edges. For 3-regular bipartite graphs, we show that if p≤4 there is a set R with |R|=p for which perfect matchings M_k exist with |M_k∩R|≤k for all k≤p. For trees we design a linear time algorithm to determine a minimum set R of red edges such that there exist maximum matchings with k red edges for the largest possible number of values of k.     

Quasi‐symmetric designs with fixed difference of block intersection numbers

The following results for proper quasi‐symmetric designs with non‐zero intersection numbers x,y and λ > 1 are proved.

• (1) Let D be a quasi‐symmetric design with z = y ? x and v ≥ 2k. If x ≥ 1 + z + z³ then λ < x + 1 + z + z³.
• (2) Let D be a quasi‐symmetric design with intersection numbers x, y and y ? x = 1. Then D is a design with parameters v = (1 + m) (2 + m)/2, b = (2 + m) (3 + m)/2, r = m + 3, k = m + 1, λ = 2, x = 1, y = 2 and m = 2,3,… or complement of one of these design or D is a design with parameters v = 5, b = 10, r = 6, k = 3, λ = 3, and x = 1, y = 2.
• (3) Let D be a triangle free quasi‐symmetric design with z = y ? x and v ≥ 2k, then x ≤ z + z².
• (4) For fixed z ≥ 1 there exist finitely many triangle free quasi‐symmetric designs non‐zero intersection numbers x, y = x + z.
• (5) There do not exist triangle free quasi‐symmetric designs with non‐zero intersection numbers x, y = x + 2.

© 2006 Wiley Periodicals, Inc. J Combin Designs 15: 49–60, 2007     

The Ramsey property for graphs with forbidden complete subgraphs

The following theorem is proved: Let G be a finite graph with cl(G) = m, where cl(G) is the maximum size of a clique in G. Then for any integer r ≥ 1, there is a finite graph H, also with cl(H) = m, such that if the edges of H are r-colored in any way, then H contains an induced subgraph G′ isomorphic to G with all its edges the same color.     

Non Existence of Triangle Free Quasi-symmetric Designs

The following two results are proved. Let D be a triangle free quasi-symmetric design with k=2y−x and x≥ 1 then D is a trivial design with v=5 and k=3. There do no exist triangle free quasi-symmetric designs with x≥ 1 and λ=y or λ=y−1.Communicated by: P. Wild     

Computing solutions for matching games

A matching game is a cooperative game (N, v) defined on a graph G = (N, E) with an edge weighting w: E? \mathbb R₊{w: E\to {\mathbb R}_+}. The player set is N and the value of a coalition S í N{S \subseteq N} is defined as the maximum weight of a matching in the subgraph induced by S. First we present an O(nm + n ² log n) algorithm that tests if the core of a matching game defined on a weighted graph with n vertices and m edges is nonempty and that computes a core member if the core is nonempty. This algorithm improves previous work based on the ellipsoid method and can also be used to compute stable solutions for instances of the stable roommates problem with payments. Second we show that the nucleolus of an n-player matching game with a nonempty core can be computed in O(n ⁴) time. This generalizes the corresponding result of Solymosi and Raghavan for assignment games. Third we prove that is NP-hard to determine an imputation with minimum number of blocking pairs, even for matching games with unit edge weights, whereas the problem of determining an imputation with minimum total blocking value is shown to be polynomial-time solvable for general matching games.     

On a criterion for the complete controllability of nonautonomous linear systems

We describe the controllability sets of linear nonautonomous systems ẋ = A(t)x + B(t)u, x ∈ ℝ ⁿ , u ∈ U ⊆ ℝ ^m , with entire matrix functions A(t) and B(t) and with a linear set U of control constraints. We derive a criterion for the complete controllability of these linear systems in terms of derivatives of the entire matrix functions A(t) and B(t) at zero. This complete controllability criterion is compared with the Kalman and Krasovskii criteria.     

List‐coloring the square of a subcubic graph

The square G² of a graph G is the graph with the same vertex set G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that every planar graph G with maximum degree Δ(G) = 3 satisfies χ(G²) ≤ 7. Kostochka and Woodall conjectured that for every graph, the list‐chromatic number of G² equals the chromatic number of G², that is, χ_l(G²) = χ(G²) for all G. If true, this conjecture (together with Thomassen's result) implies that every planar graph G with Δ(G) = 3 satisfies χ_l(G²) ≤ 7. We prove that every connected graph (not necessarily planar) with Δ(G) = 3 other than the Petersen graph satisfies χ_l(G²) ≤8 (and this is best possible). In addition, we show that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 7, then χ_l(G²) ≤ 7. Dvo?ák, ?krekovski, and Tancer showed that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 10, then χ_l(G²) ≤6. We improve the girth bound to show that if G is a planar graph with Δ(G) = 3 and g(G) ≥ 9, then χ_l(G²) ≤ 6. All of our proofs can be easily translated into linear‐time coloring algorithms. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 65–87, 2008     

Graphs with given group and given constant link

A graph L is called a link graph if there is a graph G such that for each vertex of G its neighbors induce a subgraph isomorphic to L. Such a G is said to have constant link .L Sabidussi proved that for any finite group F and any n ? 3 there are infinitely many n-regular connected graphs G with AutG ? Γ. We will prove a stronger result: For any finite group Γ and any link graph L with at least one isolated vertex and at least three vertices there are infinitely many connected graphs G with constant link L and AutG ? Γ.