Locally Well-Dominated and Locally Independent Well-Dominated Graphs

 In this article we present characterizations of locally well-dominated graphs and locally independent well-dominated graphs, and a sufficient condition for a graph to be k-locally independent well-dominated. Using these results we show that the irredundance number, the domination number and the independent domination number can be computed in polynomial time within several classes of graphs, e.g., the class of locally well-dominated graphs. Received: September 13, 2001 Final version received: May 17, 2002 RID="*" ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093) RID="†" ID="†" Supported by RUTCOR RID="*" ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093) 05C75, 05C69 Acknowledgments. The authors thank the referees for valuable suggestions.     

ON NUMBER OF LEAVES ANDBANDWIDTH OF TREES

1.IntroductionFOragraphG=(V,E)oforderp,aonetoonemappingfromVinto{l,2,',p}iscalledanumberingofG.Definition1.1.SupposefisanumberingofG.LetBj(G)=(u57teif(u)--f(v)l.ThebandwidthofG,denotedbyB(G),isdefinedbyB(G)=min{Bf(G)IfisanumberingofG}.Thebandwidthproblemofgraphshasbecomeveryimportantsincethemid-sixties(see[21or[4]).Itisverydifficulttodeterminethebandwidthofagraph.GareyetallllshowedthatthebandwidthproblemisNP-completeevenifitisrestrictedtotreeswithmaximumdegree3.Soitisinterestingtoe…     

The Clique Numbers of Regular Graphs

 Let ω(G) be the clique number of a graph G. We prove that if G runs over the set of graphs with a fixed degree sequence d, then the values ω(G) completely cover a line segment [a,b] of positive integers. For an arbitrary graphic degree sequence d, we define min(ω,d) and max(ω,d) as follows:

On Bipartite Graphs with Linear Ramsey Numbers

Dedicated to the memory of Paul Erdős We provide an elementary proof of the fact that the ramsey number of every bipartite graph H with maximum degree at most is less than . This improves an old upper bound on the ramsey number of the n-cube due to Beck, and brings us closer toward the bound conjectured by Burr and Erdős. Applying the probabilistic method we also show that for all and there exists a bipartite graph with n vertices and maximum degree at most whose ramsey number is greater than for some absolute constant c>1. Received December 1, 1999 RID="*" ID="*" Supported by NSF grant DMS-9704114 RID="**" ID="**" Supported by KBN grant 2 P03A 032 16     

Maximal Energy Bipartite Graphs

 Given a graph G, its energy E(G) is defined to be the sum of the absolute values of the eigenvalues of G. This quantity is used in chemistry to approximate the total π-electron energy of molecules and in particular, in case G is bipartite, alternant hydrocarbons. Here we show that if G is a bipartite graph with n vertices, then

Van Kampen’s embedding obstruction for discrete groups

We give a lower bound to the dimension of a contractible manifold on which a given group can act properly discontinuously. In particular, we show that the n-fold product of nonabelian free groups cannot act properly discontinuously on ℝ^{2 n −1}. Oblatum 19-I-2001 & 29-V-2002?Published online: 5 September 2002 RID="*" ID="*"All three authors gratefully acknowledge the support by the National Science Foundation.     

Some observations on Babu\vs}ka and Brezzi theories

Summary. Some observations are made on abstract error estimates for Galerkin approximations based on Babuška-Brezzi conditions. A basic error estimate due to Babuška is sharpened by means of an identity that for any nontrivial idempotent operator P. Some remarks are also made on the Brezzi's theory for mixed variational problems and their Galerkin approximations. Received March 1, 2000 / Revised version received September 28, 2000 / Published online June 17, 2002 RID="*" ID="*" This work was partially supported by NSF DMS-9706949, NSF ACI-9800244 and NASA NAG2-1236 Correspondence to: J. Xu     

Addenda to “The entropy formula for linear heat equation”

We add two sections to [8] and answer some questions asked there. In the first section we give another derivation of Theorem 1.1 of [8], which reveals the relation between the entropy formula, (1.4) of [8], and the well-known Li-Yau ’s gradient estimate. As a by-product we obtain the sharp estimates on ‘Nash’s entropy’ for manifolds with nonnegative Ricci curvature. We also show that the equality holds in Li-Yau’s gradient estimate, for some positive solution to the heat equation, at some positive time, implies that the complete Riemannian manifold with nonnegative Ricci curvature is isometric to ℝ ⁿ .In the second section we derive a dual entropy formula which, to some degree, connects Hamilton’s entropy with Perelman ’s entropy in the case of Riemann surfaces.     

Équivalence rationnelle sur les hypersurfaces cubiques sur les corps <Emphasis Type="Italic">p</Emphasis>-adiques

 We study R-equivalence on cubic hypersurfaces, and explain how to construct families of rational curves. We show that for a smooth cubic hypersurface defined over a number field K, the Chow group of zero-cycles of degree 0 is trivial in almost every place of K. Received: 20 March 2002 Published online: 24 January 2003     

A primal all-integer algorithm based on irreducible solutions

 This paper introduces an exact primal augmentation algorithm for solving general linear integer programs. The algorithm iteratively substitutes one column in a tableau by other columns that correspond to irreducible solutions of certain linear diophantine inequalities. We prove that various versions of our algorithm are finite. It is a major concern in this paper to show how the subproblem of replacing a column can be accomplished effectively. An implementation of the presented algorithms is given. Computational results for a number of hard 0/1 integer programs from the MIPLIB demonstrate the practical power of the method. Received: April 23, 2001 / Accepted: May 2002 Published online: March 21, 2003 RID="*" ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. RID="*" ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. RID="*" ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. RID="#" ID="#"Supported by a Gerhard-Hess-Preis and grant WE 1462 of the Deutsche Forschungsgemeinschaft, and by the European DONET program TMR ERB FMRX-CT98-0202. Mathematics Subject Classification (1991): 90C10     

Laminations and groups of homeomorphisms of the circle

If M is an atoroidal 3-manifold with a taut foliation, Thurston showed that π₁(M) acts on a circle. Here, we show that some other classes of essential laminations also give rise to actions on circles. In particular, we show this for tight essential laminations with solid torus guts. We also show that pseudo-Anosov flows induce actions on circles. In all cases, these actions can be made into faithful ones, so π₁(M) is isomorphic to a subgroup of Homeo(S ¹). In addition, we show that the fundamental group of the Weeks manifold has no faithful action on S ¹. As a corollary, the Weeks manifold does not admit a tight essential lamination with solid torus guts, a pseudo-Anosov flow, or a taut foliation. Finally, we give a proof of Thurston’s universal circle theorem for taut foliations based on a new, purely topological, proof of the Leaf Pocket Theorem. Oblatum 20-III-2002 & 30-IX-2002?Published online: 18 December 2002 RID="*" ID="*"Both authors partially supported by the U.S. National Science Foundation.     

On the Oka principle in a Banach space,I

 Let X be a complex Banach space with a countable unconditional basis, Ω⊂X pseudoconvex open, G a complex Banach Lie group. We show that a Runge–type approximation hypothesis on X, G (which we also prove for G a solvable Lie group) implies that any holomorphic cocycle on Ω with values in G can be resolved holomorphically if it can be resolved continuously. Received: 1 March 2002 / Published online: 28 March 2003 Mathematics Subject Classification (2000): 32L05, 32E30, 46G20 RID="*" ID="*" Kedves Szímuskának. RID="*" ID="*" To my dear Wife.     

Simple and immune relations on countable structures

 Let 𝒜 be a computable structure and let R be a new relation on its domain. We establish a necessary and sufficient condition for the existence of a copy ℬ of 𝒜 in which the image of R (?R, resp.) is simple (immune, resp.) relative to ℬ. We also establish, under certain effectiveness conditions on 𝒜 and R, a necessary and sufficient condition for the existence of a computable copy ℬ of 𝒜 in which the image of R (?R, resp.) is simple (immune, resp.). Received: 4 February 2001 Published online: 5 November 2002 RID="*" ID="*" The first three authors gratefully acknowledge support of the NFS Binational Grant DMS-0075899. RID="*" ID="*" The first three authors gratefully acknowledge support of the NFS Binational Grant DMS-0075899. RID="*" ID="*" The first three authors gratefully acknowledge support of the NFS Binational Grant DMS-0075899.     

Integral bounds for simple partial fractions

For p ≥ 2 we obtain bounds for L _p -norms of the Fourier transform of real parts of simple partial fractions. For even p our estimate is sharp. We also prove a new inequality for L _p -norms of simple partial fractions which in some cases is stronger than the corresponding inequality obtained by V. Yu. Protasov.     

Iwasawa theory for elliptic curves at supersingular primes

We give a new formulation in Iwasawa theory for elliptic curves at good supersingular primes. This formulation is similar to Mazur’s at good ordinary primes. Namely, we define a new Selmer group, and show that it is of Λ-cotorsion. Then we formulate the Iwasawa main conjecture as that the characteristic ideal is generated by Pollack’s p-adic L-function. We show that this main conjecture is equivalent to Kato’s and Perrin-Riou’s main conjectures. We also prove an inequality in the main conjecture by using Kato’s Euler system. In terms of the λ- and the μ-invariants of our Selmer group, we specify the numbers λ and μ in the asymptotic formula for the order of the Tate-Shafarevich group by Kurihara and Perrin-Riou. Oblatum 17-VI-2002 & 2-IX-2002?Published online: 18 December 2002     

Pathwidth of Planar and Line Graphs

 We prove that for every 2-connected planar graph the pathwidth of its geometric dual is less than the pathwidth of its line graph. This implies that pathwidth(H)≤ pathwidth(H ^*)+1 for every planar triangulation H and leads us to a conjecture that pathwidth(G)≤pathwidth(G ^*)+1 for every 2-connected graph G. Received: May 8, 2001 Final version received: March 26, 2002 RID="*" ID="*" I acknowledge support by EC contract IST-1999-14186, Project ALCOM-FT (Algorithms and Complexity - Future Technologies) and support by the RFBR grant N01-01-00235. Acknowledgments. I am grateful to Petr Golovach, Roland Opfer and anonymous referee for their useful comments and suggestions.     

Doubling and Tripling Constructions for Defining Sets in Steiner Triple Systems

 A minimal defining set of a Steiner triple system on v points (STS(v)) is a partial Steiner triple system contained in only this STS(v), and such that any of its proper subsets is contained in at least two distinct STS(v)s. We consider the standard doubling and tripling constructions for STS(2v+1) and STS(3v) from STS(v) and show how minimal defining sets of an STS(v) gives rise to minimal defining sets in the larger systems. We use this to construct some new families of defining sets. For example, for Steiner triple systems on 3 ⁿ points, we construct minimal defining sets of volumes varying by as much as 7 ⁿ⁻² . Received: September 16, 2000 Final version received: September 13, 2001 RID="*" ID="*" Research supported by the Australian Research Council A49937047, A49802044     

The Turán-Kubilius inequality for additive arithmetical semigroups

We show that the Turán-Kubilius inequality holds for additive arithmetical semigroups satisfying the following conditions: G(n) = q ⁿ (A+O(1/ln n)) (where A > 0 and q > 1) for the number of elements of degree n and P(n) = O(q ⁿ /n) for the number of prime elements of degree n. This is an improvement of a result of Zhang. We also give some variants of the inequality under some stronger or weaker assumptions and applications for the prime divisor function ω and related functions. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 46, No. 3, pp. 457–471, July–September, 2006.