Geometry and algebra of real forms of complex curves

Let Y be a complex algebraic curve and let be the set of all real algebraic curves with complexification , such that the real points divide . We find all such families [Y]. According to Harnak theorem a number of connected components of satisfies by the inequality , where g is the genus of Y. We prove that and these estimates are exact. Received: 15 November 2001; in final form: 28 April 2002/Published online: 2 December 2002     

Unit squares intersecting all secants of a square

LetS be a square of side lengths>0. We construct, for any sufficiently larges, a set of less than 1.994s closed unit squares whose sides are parallel to those ofS such that any straight line intersectingS intersects at least one square ofS. It disproves L. Fejes Tóth's conjecture that, for integrals, there is no such configuration of less than 2s−1 unit squares. Supported by “Deutsche Forschungsgemeinschaft”, Grant We 1265/2-1.     

Complex Symplectic Geometry of Quasi-Fuchsian Space

We study the complex symplectic geometry of the space QF(S) of quasi-Fuchsian structures of a compact orientable surface S of genus g > 1. We prove that QF(S) is a complex symplectic manifold. The complex symplectic structure is the complexification of the Weil–Petersson symplectic structure of Teichmüller space and is described in terms which look natural from the point of view of hyperbolic geometry.     

Magnetohydrodynamic shear flow along a flat plate with uniform suction or blowing

An analysis is made of the steady shear flow of an incompressible viscous electrically conducting fluid past an electrically insulating porous flat plate in the presence of an applied uniform transverse magnetic field. It is shown that steady shear flow exists for suction at the plate only when the square of the suction parameter S is less than the magnetic parameter Q. In this case the velocity at a given point increases with increase in either the magnetic field or suction velocity. The shear stress at the plate increases with increase in either S or the free-stream shear-rate parameter σ₁ or Q. The analysis further reveals that solution exists for steady shear flow past a porous flat plate subject to blowing only when the square of the blowing parameter S₁ is less than Q. It is found that the induced magnetic field at a given location decreases with increase in Q. Further the wall shear stress decreases with increase in S₁. No steady shear flow is possible for blowing at the plate when S₁² > Q. Received: June 16, 2004; revised: October 24, 2004     

Intersection formulae for the kernel of a cone

A subset S of Euclidean space is called a cone if it is the union of a set of halflines having the same endpoint called the apex of the cone, and the set of all such apices is denoted by ker _R S and called the R-kernel or, when it does not lead to any confusion with the kernel of a starshaped set, simply the kernel of S. ker _R S is shown to be the intersection of a family of flats passing through some selected boundary points of S. Three independent formulae of this type are established, respectively: for an arbitrary proper subset S, for S closed, and for S closed connected and nonconvex.The author is with the Department of Mathematics, University of Notre Dame, Indiana, on leave from the Mathematical Institute of the Polish Academy of Sciences.     

Characterizations of trees with equal domination parameters

Let G = (V, E) be a graph. A set S ⊆ V is a restrained dominating set, if every vertex not in S is adjacent to a vertex in S and to a vertex in V − S. The restrained domination number of G, denoted by γ_r(G), is the minimum cardinality of a restrained dominating set of G. A set S ⊆ V is a weak dominating set of G if, for every u in V − S, there exists a v ∈ S such that uv ∈ E and deg u ≥ deg v. The weak domination number of G, denoted by γ_w(G), is the minimum cardinality of a weak dominating set of G. In this article, we provide a constructive characterization of those trees with equal independent domination and restrained domination numbers. A constructive characterization of those trees with equal independent domination and weak domination numbers is also obtained. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 142–153, 2000     

Maximizing Voronoi Regions of a Set of Points Enclosed in a Circle with Applications to Facility Location

In this paper we introduce an optimization problem which involves maximization of the area of Voronoi regions of a set of points placed inside a circle. Such optimization goals arise in facility location problems consisting of both mobile and stationary facilities. Let ψ be a circular path through which mobile service stations are plying, and S be a set of n stationary facilities (points) inside ψ. A demand point p is served from a mobile facility plying along ψ if the distance of p from the boundary of ψ is less than that from any member in S. On the other hand, the demand point p is served from a stationary facility p _i  ∈ S if the distance of p from p _i is less than or equal to the distance of p from all other members in S and also from the boundary of ψ. The objective is to place the stationary facilities in S, inside ψ, such that the total area served by them is maximized. We consider a restricted version of this problem where the members in S are placed equidistantly from the center o of ψ. It is shown that the maximum area is obtained when the members in S lie on the vertices of a regular n-gon, with its circumcenter at o. The distance of the members in S from o and the optimum area increases with n, and at the limit approaches the radius and the area of the circle ψ, respectively. We also consider another variation of this problem where a set of n points is placed inside ψ, and the task is to locate a new point q inside ψ such that the area of the Voronoi region of q is maximized. We give an exact solution of this problem when n = 1 and a (1 − ε)-approximation algorithm for the general case.     

Off-line dynamic maintenance of the width of a planar point set

Agarwal, P.K. and M. Sharir, Off-line dynamic maintenance of the width of a planar point set, Computational Geometry: Theory and Applications 1 (1990) 65-78. In this paper we present an efficient algorithm for the off-line dynamic maintenance of the width of a planar point set in the following restricted case: We are given a real parameter W and a sequence Σ=(σ₁,...,σ_n) of n insert and delete operations on a set S of points in ², initially consisting of n points, and we want to determine whether there is an i such that the width of S the ith operation is less than or equal to W. Our algorithm runs in time O(nlog³n) and uses O(n) space.     

Small dilatation pseudo-Anosov homeomorphisms and 3-manifolds

The main result of this paper is a universal finiteness theorem for the set of all small dilatation pseudo-Anosov homeomorphisms ?:S→S, ranging over all surfaces S. More precisely, we consider pseudo-Anosov homeomorphisms ?:S→S with |χ(S)|log(λ(?)) bounded above by some constant, and we prove that, after puncturing the surfaces at the singular points of the stable foliations, the resulting set of mapping tori is finite. Said differently, there is a finite set of fibered hyperbolic 3-manifolds so that all small dilatation pseudo-Anosov homeomorphisms occur as the monodromy of a Dehn filling on one of the 3-manifolds in the finite list, where the filling is on the boundary slope of a fiber.     

Points of local nonconvexity and sets which are almost starshaped

Let Sø be a bounded connected set in R ², and assume that every 3 or fewer lnc points of S are clearly visible from a common point of S. Then for some point p in S, the set A{s : s in S and [p, s] S} is nowhere dense in S. Furthermore, when S is open, then S in starshaped.     

Domination versus disjunctive domination in graphs

A dominating set in a graph G is a set S of vertices of G such that every vertex not in S is adjacent to a vertex of S. The domination number of G is the minimum cardinality of a dominating set of G. For a positive integer b, a set S of vertices in a graph G is a b-disjunctive dominating set in G if every vertex v not in S is adjacent to a vertex of S or has at least b vertices in S at distance 2 from it in G. The b-disjunctive domination number of G is the minimum cardinality of a b-disjunctive dominating set. In this paper, we continue the study of disjunctive domination in graphs. We present properties of b-disjunctive dominating sets in a graph. A characterization of minimal b-disjunctive dominating sets is given. We obtain bounds on the ratio of the domination number and the b-disjunctive domination number for various families of graphs, including regular graphs and trees.     

The Convexity Number of a Graph

 For two vertices u and v of a connected graph G, the set I[u,v] consists of all those vertices lying on a u−v shortest path in G, while for a set S of vertices of G, the set I[S] is the union of all sets I[u,v] for u,v∈S. A set S is convex if I[S]=S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. The clique number ω(G) is the maximum cardinality of a clique in G. If G is a connected graph of order n that is not complete, then n≥3 and 2≤ω(G)≤con(G)≤n−1. It is shown that for every triple l,k,n of integers with n≥3 and 2≤l≤k≤n−1, there exists a noncomplete connected graph G of order n with ω(G)=l and con(G)=k. Other results on convex numbers are also presented. Received: August 19, 1998 Final version received: May 17, 2000     

Paths extendable to cycles

Let k be a positive integer, and S a nonempty set of positive integers. Suppose that G is a connected graph containing a path of length k, and that each path P of length k in G is contained in some cycle C(P) of length s ∈ S. We prove that every path of length less than k can be extended to a path of length k in G. This result answers conjectures of Entringer and Reid regarding when certain paths may be extended to cycles.     

Integral trees of arbitrarily large diameters

In this paper, we construct trees having only integer eigenvalues with arbitrarily large diameters. In fact, we prove that for every finite set S of positive integers there exists a tree whose positive eigenvalues are exactly the elements of S. If the set S is different from the set {1} then the constructed tree will have diameter 2|S|.     

Constructive characterizations of （γp, γ）- and （γp, γpr）-trees

Let G = （V, E） be a graph without isolated vertices. A set S lohtain in V is a domination set of G if every vertex in V - S is adjacent to a vertex in S, that is N[S] = V. The domination number of G, denoted by γ（G）, is the minimum cardinality of a domination set of G. A set S lohtain in V is a paired-domination set of G if S is a domination set of G and the induced subgraph G[S] has a perfect matching. The paired-domination number, denoted by γpr（G）, is defined to be the minimum cardinality of a paired-domination set S in G. A subset S lohtain in V is a power domination set of G if all vertices of V can be observed recursively by the following rules： （i） all vertices in N[S] are observed initially, and （ii） if an observed vertex u has all neighbors observed except one neighbor v, then v is observed （by u）. The power domination number, denoted by γp（G）, is the minimum cardinality of a power domination set of G. In this paper, the constructive characterizations for trees with γp=γ and γpr = γp are provided respectively.     

Intersection of maximal orthogonally starshaped polygons

Let S be a simply connected orthogonal polygon in and let P(S) denote the intersection of all maximal starshaped via staircase paths orthogonal subpolygons in S. Our result: if , then there exists a maximal starshaped via staircase paths orthogonal polygon , such that . As a corollary, P(S) is a starshaped (via staircase paths) orthogonal polygon or empty. The results fail without the requirement that the set S is simply connected. Received 1 March 1999.     

On the sum of the total domination numbers of a digraph and its converse

A vertex subset S of a digraph D is called a dominating set of D if every vertex not in S has an in-neighbor in S. A dominating set S of D is called a total dominating set of D if the subdigraph induced by S has no isolated vertices. The total domination number of D, denoted by γt(D), is the minimum cardinality of a total dominating set of D. We show that for any connected digraph D of order n≥3, γt(D)+γt(D^? )≤5n/3, where D? is the converse of D. Furthermore, we characterize the oriented trees for which the equality holds.     

Adelic version of Margulis arithmeticity theorem

We generalize Margulis's S-arithmeticity theorem to the case when S can be taken as an infinite set of primes. Let R be the set of all primes including infinite one and set . Let S be any subset of R. For each , let be a connected semisimple adjoint -group and be a compact open subgroup for each finite prime . Let denote the restricted topological product of 's, with respect to 's. Note that if S is finite, . We show that if , any irreducible lattice in is a rational lattice. We also present a criterion on the collections and for to admit an irreducible lattice. In addition, we describe discrete subgroups of generated by lattices in a pair of opposite horospherical subgroups. Received: 30 November 2000 / Revised version: 2 April 2001 / Published online: 24 September 2001     

A solution to a problem of Cameron on sum-free complete sets

For any subsets A and B of an additive group G, define A + B = { a + b: a ε A and b ε B} and −A = {−a: a ε A}. A subset S of G is said to be sum-free, complete, and symmetric respectively if S + S S^c, S + S S^c, and S = −S. Cameron asked if for all sufficiently large moduli m there exists a sum-free complete set in Z/mZ that is not symmetric. We answer Cameron's question by showing there exists such a set for all moduli greater than or equal to 890626. We also show that every sum-free complete set in Z/mZ that is not symmetric can be used to construct a counter-example to a conjecture of Conway disproved by Marica. Conway conjectured that for any finite set S of integers, |S + S| |S --- S|.     

On the multiple Borsuk numbers of sets

The Borsuk number of a set S of diameter d > 0 in Euclidean n-space is the smallest value of m such that S can be partitioned into m sets of diameters less than d. Our aim is to generalize this notion in the following way: The k -fold Borsuk number of such a set S is the smallest value of m such that there is a k-fold cover of S with m sets of diameters less than d. In this paper we characterize the k-fold Borsuk numbers of sets in the Euclidean plane, give bounds for those of centrally symmetric sets, smooth bodies and convex bodies of constant width, and examine them for finite point sets in the Euclidean 3-space.