共查询到20条相似文献,搜索用时 31 毫秒
1.
Dedicated to the memory of Paul Erdős
A graph is called H-free if it contains no induced copy of H. We discuss the following question raised by Erdős and Hajnal. Is it true that for every graph H, there exists an such that any H-free graph with n vertices contains either a complete or an empty subgraph of size at least ? We answer this question in the affirmative for a special class of graphs, and give an equivalent reformulation for tournaments.
In order to prove the equivalence, we establish several Ramsey type results for tournaments.
Received August 22, 1999
RID="*"
ID="*" Supported by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva
Center for Geometry at Tel Aviv University.
RID="†"
ID="†" Supported by NSF grant CR-9732101, PSC-CUNY Research Award 663472, and OTKA-T-020914.
RID="‡"
ID="‡" Supported by TKI grant Stochastics@TUB, and OTKA-T-026203. 相似文献
2.
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 相似文献
3.
Dedicated to the memory of Paul Erdős
Let H be a simple graph having no isolated vertices. An (H,k)-vertex-cover of a simple graph G = (V,E) is a collection of subgraphs of G satisfying
1. , for all i = 1, ..., r,
2. ,
3. , for all , and
4. each is in at most k of the . We consider the existence of such vertex covers when H is a complete graph, , in the context of extremal and random graphs.
Received October 31, 1999
RID="*"
ID="*" Supported in part by NSF grant DMS-9627408.
RID="†"
ID="†" Supported in part by NSF grant CCR-9530974.
RID="‡"
ID="‡" Supported in part by OTKA Grants T 030059 and T 29074, FKFP 0607/1999 and by the Bolyai Foundation.
RID="§"
ID="§" Supported in part by NSF grant DMS-9970622. 相似文献
4.
Summary. We derive error bounds for bivariate spline interpolants which are calculated by minimizing certain natural energy norms.
Received March 28, 2000 / Revised version received June 23, 2000 / Published online March 8, 2002
RID="*"
ID="*" Supported by the National Science Foundation under grant DMS-9870187
RID="**"
ID="**" Supported by the National Science Foundation under grant DMS-9803340 and by the Army Research Office under grant DAAD-19-99-1-0160 相似文献
5.
6.
I. Albarreal M.C. Calzada J.L. Cruz E. Fernández-Cara J. Galo M. Marín 《Numerische Mathematik》2002,93(2):201-221
Summary. This paper is concerned with the analysis of the convergence and the derivation of error estimates for a parallel algorithm
which is used to solve the incompressible Navier-Stokes equations. As usual, the main idea is to split the main differential
operator; this allows to consider independently the two main difficulties, namely nonlinearity and incompressibility. The
results justify the observed accuracy of related numerical results.
Received April 20, 2001 / Revised version received May 21, 2001 / Published online March 8, 2002
RID="*"
ID="*" Partially supported by D.G.E.S. (Spain), Proyecto PB98–1134
RID="**"
ID="**" Partially supported by D.G.E.S. (Spain), Proyecto PB96–0986
RID="**"
ID="**" Partially supported by D.G.E.S. (Spain), Proyecto PB96–0986
RID="*"
ID="*" Partially supported by D.G.E.S. (Spain), Proyecto PB98–1134
RID="**"
ID="**" Partially supported by D.G.E.S. (Spain), Proyecto PB96–0986
RID="**"
ID="**" Partially supported by D.G.E.S. (Spain) Proyecto PB96–0986 相似文献
7.
Dedicated to the memory of Paul Erdős
In [9] Thomassen proved that a -connected graph either contains k vertex disjoint odd cycles or an odd cycle cover containing at most 2k-2 vertices, i.e. he showed that the Erdős–Pósa property holds for odd cycles in highly connected graphs. In this paper, we
will show that the above statement is still valid for 576k-connected graphs which is essentially best possible.
Received November 17, 1999
RID="*"
ID="*" This work was supported by a post-doctoral DONET grant.
RID="†"
ID="†" This work was supported by an NSF-CNRS collaborative research grant.
RID="‡"
ID="‡" This work was performed while both authors were visiting the LIRMM, Université de Montpellier II, France. 相似文献
8.
Let V be a simple vertex operator algebra and G a finite automorphism group. Then there is a natural right G-action on the set of all inequivalent irreducible V-modules. Let be a finite set of inequivalent irreducible V-modules which is closed under the action of G. There is a finite dimensional semisimple associative algebra for a suitable 2-cocycle naturally determined by the G-action on such that and the vertex operator algebra form a dual pair on the sum of V-modules in in the sense of Howe. In particular, every irreducible V-module is completely reducible -module.
Received: 10 September, 2001 / Published online: 29 April 2002
RID="*"
ID="*" Supported by NSF grants and a research grant from the Committee on Research, UC Santa Cruz.
RID="**"
ID="**" Supported by DPST grant from government of Thailand. 相似文献
9.
Michael Capalbo 《Combinatorica》2002,22(3):345-359
For all positive integers N and k, let denote the family of planar graphs on N or fewer vertices, and with maximum degree k. For all positive integers N and k, we construct a -universal graph of size . This construction answers with an explicit construction the previously open question of the existence of such a graph.
Received July 8, 1998
RID="*"
ID="*" Supported by NSF grant CCR98210-58 and ARO grant DAAH04-96-1-0013. 相似文献
10.
In this work we analyze the paper “Brimberg, J. (1995): The Fermat-Weber location problem revisited. Mathematical Programming 71, 71–76” which claims to close the question on the conjecture posed by Chandrasekaran and Tamir in 1989 on the convergence
of the Weiszfeld algorithm. Some counterexamples are shown to the proofs showed in Brimberg’s paper.
Received: January 1999 / Accepted: December 2001?Published online April 12, 2002
RID="*"
ID="*"Partially supported by PB/11/FS/97 of Fundación Séneca of the Comunidad Autónoma de la Región de Murcia
RID="**"
ID="**"Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica (I+I+D), project TIC2000-1750-C06-06
RID="*"
RID="**" 相似文献
11.
Graph Orientations with Edge-connection and Parity Constraints 总被引:2,自引:0,他引:2
Parity (matching theory) and connectivity (network flows) are two main branches of combinatorial optimization. In an attempt
to understand better their interrelation, we study a problem where both parity and connectivity requirements are imposed.
The main result is a characterization of undirected graphs G = (V,E) having a k-edge-connected T-odd orientation for every subset with |E| + |T| even. (T-odd orientation: the in-degree of v is odd precisely if v is in T.) As a corollary, we obtain that every (2k)-edge-connected graph with |V| + |E| even has a (k-1)-edge-connected orientation in which the in-degree of every node is odd. Along the way, a structural characterization will
be given for digraphs with a root-node s having k edge-disjoint paths from s to every node and k-1 edge-disjoint paths from every node to s.
Received December 14, 1998/Revised January 12, 2001
RID="*"
ID="*" Supported by the Hungarian National Foundation for Scientific Research, OTKA T029772. Part of research was done while
this author was visiting EPFL, Lausanne, June, 1998.
RID="†"
ID="†" Supported by the Hungarian National Foundation for Scientific Research, OTKA T029772 and OTKA T030059. 相似文献
12.
Sándor Jenei 《Archive for Mathematical Logic》2003,42(5):489-514
We generalize the notions of Girard algebras and MV-algebras by introducing rotation-invariant semigroups. Based on a geometrical
characterization, we present five construction methods which result in rotation-invariant semigroups and in particular, Girard
algebras and MV-algebras. We characterize divisibility of MV-algebras, and point out that integrality of Girard algebras follows
from their other axioms.
Received: 7 January 2002 / Revised version: 4 April 2002 /
Published online: 19 December 2002
RID="*"
ID="*" Supported by the National Scientific Research Fund Hungary (OTKA F/032782).
Mathematics Subject Classification (2000): 20M14, 06F05
Key words or phrases: Residuated lattice – Conjunction for non-classical logics 相似文献
13.
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. 相似文献
14.
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 相似文献
15.
We study homotopy equivalences of p-completions of classifying spaces of finite groups. To each finite group G and each prime p, we associate a finite category ℒ
p
c
(G) with the following properties. Two p-completed classifying spaces BG
p
∧ and BG’
p
∧ have the same homotopy type if and only if the associated categories ℒ
p
c
(G) and ℒ
p
c
(G’) are equivalent. Furthermore, the topological monoid Aut(BG
p
∧) of self equivalences is determined by the self equivalences of the associated category ℒ
p
c
(G).
Oblatum 5-VII-2001 & 28-VIII-2002?Published online: 8 November 2002
RID="*"
ID="*"C. Broto is partially supported by DGICYT grant PB97–0203.
RID="**"
ID="**"R. Levi is partially supported by EPSRC grant GR/M7831.
RID="***"
ID="***"B. Oliver is partially supported by UMR 7539 of the CNRS. 相似文献
16.
It is proved that, for any ɛ>0 and n>n
0(ɛ), every set of n points in the plane has at most triples that induce isosceles triangles. (Here e denotes the base of the natural logarithm, so the exponent is roughly 2.136.) This easily implies the best currently known
lower bound, , for the smallest number of distinct distances determined by n points in the plane, due to Solymosi–Cs. Tóth and Tardos.
Received: February, 2002 Final version received: September 15, 2002
RID="*"
ID="*" Supported by NSF grant CCR-00-86013, PSC-CUNY Research Award 63382-00-32, and OTKA-T-032452
RID="†"
ID="†" Supported by OTKA-T-030059 and AKP 2000-78-21 相似文献
17.
Bojan Mohar 《Combinatorica》2001,21(3):395-401
It is proved that the decision problem about the existence of an embedding of face-width 3 of a given graph is NP-complete. A similar result is proved for some related decision problems. This solves a problem raised by Neil Robertson.
Received July 6, 1998
RID="*"
ID="*" Supported in part by the Ministry of Science and Technology of Slovenia, Research Project J1–0502–0101–98. 相似文献
18.
19.
We show that every 6-edge connected graph admits a circulation whose range lies in the interval [1,3).
Received March 29, 2000
RID="*"
ID="*" Supported by NATO-CNR Fellowship; this work was done while the author was visiting the Dept. of Mathematics and Statistics
at Simon Fraser University, Canada.
RID="†"
ID="†" Supported by a National Sciences and Engineering Research Council Research Grant 相似文献
20.
Maximal Energy Bipartite Graphs 总被引:1,自引:0,他引:1
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
must hold, characterize those bipartite graphs for which this bound is sharp, and provide an infinite family of maximal energy
bipartite graphs.
Received: December 1, 2000 Final version received: August 28, 2001
RID="*"
ID="*" The author thanks the Swedish Natural Science Research Council (NFR) – grant M12342-300 – for its support.
Acknowledgments. The authors would like to thank Ivan Gutman for encouraging them to write this paper, and for helpful discussions on this
topic. They also would like to thank Edwin van Dam for his reference concerning connected bipartite regular graphs with four
eigenvalues. 相似文献