首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
For a fixed multigraph H with vertices w1,…,wm, a graph G is H-linked if for every choice of vertices v1,…,vm in G, there exists a subdivision of H in G such that vi is the branch vertex representing wi (for all i). This generalizes the notions of k-linked, k-connected, and k-ordered graphs.Given a connected multigraph H with k edges and minimum degree at least two and n7.5k, we determine the least integer d such that every n-vertex simple graph with minimum degree at least d is H-linked. This value D(H,n) appears to equal the least integer d such that every n-vertex graph with minimum degree at least d is b(H)-connected, where b(H) is the maximum number of edges in a bipartite subgraph of H.  相似文献   

2.
If A=(Aij)1?i,j?nB(X) is an upper triangular Banach space operator such that AiiAij=AijAjj for all 1?i?j?n, then A has SVEP or satisfies (Dunford's) condition (C) or (Bishop's) property (β) or (the decomposition) property (δ) if and only if Aii, 1?i?n, has the corresponding property.  相似文献   

3.
Henry Liu  Yury Person   《Discrete Mathematics》2009,309(21):6277-6287
For integers , nk and rs, let m(n,r,s,k) be the largest (in order) k-connected component with at most s colours one can find in any r-colouring of the edges of the complete graph Kn on n vertices. Bollobás asked for the determination of m(n,r,s,k).Here, bounds are obtained in the cases s=1,2 and k=o(n), which extend results of Liu, Morris and Prince. Our techniques use Szemerédi’s Regularity Lemma for many colours.We shall also study a similar question for bipartite graphs.  相似文献   

4.
We prove a Strong Haagerup inequality with operator coefficients. If for an integer d, denotes the subspace of the von Neumann algebra of a free group FI spanned by the words of length d in the generators (but not their inverses), then we provide in this paper an explicit upper bound on the norm on , which improves and generalizes previous results by Kemp–Speicher (in the scalar case) and Buchholz and Parcet–Pisier (in the non-holomorphic setting). Namely the norm of an element of the form ∑i=(i1,…,id)aiλ(gi1gid) is less than , where M0,…,Md are d+1 different block-matrices naturally constructed from the family (ai)iId for each decomposition of IdIl×Idl with l=0,…,d. It is also proved that the same inequality holds for the norms in the associated non-commutative Lp spaces when p is an even integer, pd and when the generators of the free group are more generally replaced by *-free -diagonal operators. In particular it applies to the case of free circular operators. We also get inequalities for the non-holomorphic case, with a rate of growth of order d+1 as for the classical Haagerup inequality. The proof is of combinatorial nature and is based on the definition and study of a symmetrization process for partitions.  相似文献   

5.
For a fixed value of a parameter k≥2, the Maximum k-Edge-Colorable Subgraph Problem consists in finding k edge-disjoint matchings in a simple graph, with the goal of maximising the total number of edges used. The problem is known to be -hard for all k, but there exist polynomial time approximation algorithms with approximation ratios tending to 1 as k tends to infinity. Herein we propose improved approximation algorithms for the cases of k=2 and k=3, having approximation ratios of 5/6 and 4/5, respectively.  相似文献   

6.
Toru Araki   《Discrete Mathematics》2009,309(21):6229-6234
For a digraph G, a k-tuple twin dominating set D of G for some fixed k≥1 is a set of vertices such that every vertex is adjacent to at least k vertices in D, and also every vertex is adjacent from at least k vertices in D. If the subgraph of G induced by D is strongly connected, then D is called a connected k-tuple twin dominating set of G. In this paper, we give constructions of minimal connected k-tuple twin dominating sets for de Bruijn digraphs and Kautz digraphs.  相似文献   

7.
The core of a game v on N, which is the set of additive games φ dominating v such that φ(N)=v(N), is a central notion in cooperative game theory, decision making and in combinatorics, where it is related to submodular functions, matroids and the greedy algorithm. In many cases however, the core is empty, and alternative solutions have to be found. We define the k-additive core by replacing additive games by k-additive games in the definition of the core, where k-additive games are those games whose Möbius transform vanishes for subsets of more than k elements. For a sufficiently high value of k, the k-additive core is nonempty, and is a convex closed polyhedron. Our aim is to establish results similar to the classical results of Shapley and Ichiishi on the core of convex games (corresponds to Edmonds’ theorem for the greedy algorithm), which characterize the vertices of the core.  相似文献   

8.
In 1990, Acharya and Hegde introduced the concept of strongly k-indexable graphs: A (p,q)-graph G=(V,E) is said to be strongly k-indexable if its vertices can be assigned distinct numbers 0,1,2,…,p−1 so that the values of the edges, obtained as the sums of the numbers assigned to their end vertices form an arithmetic progression k,k+1,k+2,…,k+(q−1). When k=1, a strongly k-indexable graph is simply called a strongly indexable graph. In this paper, we report some results on strongly k-indexable graphs and give an application of strongly k-indexable graphs to plane geometry, viz; construction of polygons of same internal angles and sides of distinct lengths.  相似文献   

9.
Rather mild sufficient conditions are provided for the existence of positive solutions of a boundary value problem of the form
which unify several cases discussed in the literature. In order to formulate these conditions one needs to know only properties of the homeomorphism and have information about the level of growth of the response operator F. No metric information concerning the linear operators L0,L1 in the boundary conditions is used, except that they are positive and continuous and such that Lj(1)<1 j{0,1}.  相似文献   

10.
This study concerns the existence of positive solutions to the boundary value problemwhere ξi(0,1) with 0<ξ1<ξ2<<ξn-2<1, ai, bi[0,∞) with and . By applying the Krasnoselskii's fixed-point theorem in Banach spaces, some sufficient conditions guaranteeing the existence of at least one positive solution or at least two positive solutions are established for the above general n-point boundary value problem.  相似文献   

11.
12.
We consider the projected subgradient method for solving generalized mixed variational inequalities. In each step, we choose an εk-subgradient uk of the function f and wk in a set-valued mapping T, followed by an orthogonal projection onto the feasible set. We prove that the sequence is weakly convergent.  相似文献   

13.
We prove that fractional k-factors can be transformed among themselves by using a new adjusting operation repeatedly. We introduce, analogous to Berge’s augmenting path method in matching theory, the technique of increasing walk and derive a characterization of maximum fractional k-factors in graphs. As applications of this characterization, several results about connected fractional 1-factors are obtained.  相似文献   

14.
A subset X of an abelian group Γ, written additively, is a Sidon set of orderh if whenever {(ai,mi):iI} and {(bj,nj):jJ} are multisets of size h with elements in X and ∑iImiai=∑jJnjbj, then {(ai,mi):iI}={(bj,nj):jJ}. The set X is a generalized Sidon set of order(h,k) if whenever two such multisets have the same sum, then their multiset intersection has size at least k. It is proved that if X is a generalized Sidon set of order (2h−1,h−1), then the maximal Sidon sets of order h contained in X have the same cardinality. Moreover, X is a matroid where the independent subsets of X are the Sidon sets of order h.  相似文献   

15.
The operator of F. Bergeron, Garsia, Haiman and Tesler [F. Bergeron, A. Garsia, M. Haiman, G. Tesler, Identities and positivity conjectures for some remarkable operators in the theory of symmetric functions, Methods Appl. Anal. 6 (1999) 363–420] acting on the k-Schur functions [L. Lapointe, A. Lascoux, J. Morse, Tableaux atoms and a new Macdonald positivity conjecture, Duke Math. J. 116 (2003) 103–146; L. Lapointe, J. Morse, Schur functions analogs for a filtration of the symmetric functions space, J. Combin. Theory Ser. A 101 (2003) 191–224; L. Lapointe, J. Morse, Tableaux on k+1-cores, reduced words for affine permutations and k-Schur expansion, J. Combin. Theory Ser. A 112 (2005) 44–81] indexed by a single column has a coefficient in the expansion which is an analogue of the (q,t)-Catalan number with a level k. When k divides n we conjecture a representation theoretical model in this case such that the graded dimensions of the module are the coefficients of the (q,t)-Catalan polynomials of level k. When the parameter t is set to 1, the Catalan numbers of level k are shown to count the number of Dyck paths that lie below a certain Dyck path with q counting the area of the path.  相似文献   

16.
Let G be an edge weighted graph with n nodes, and let A(3,G) be the average weight of a triangle in G. We show that the number of triangles with weight at most equal to A(3,G) is at least (n−2) and that this bound is sharp for all n≥7. Extensions of this result to cliques of cardinality k>3 are also discussed.  相似文献   

17.
Denis S. Krotov   《Discrete Mathematics》2008,308(22):5289-5297
An n-ary operation Q:ΣnΣ is called an n-ary quasigroup of order |Σ| if in the relation x0=Q(x1,…,xn) knowledge of any n elements of x0,…,xn uniquely specifies the remaining one. Q is permutably reducible if Q(x1,…,xn)=P(R(xσ(1),…,xσ(k)),xσ(k+1),…,xσ(n)) where P and R are (n-k+1)-ary and k-ary quasigroups, σ is a permutation, and 1<k<n. An m-ary quasigroup S is called a retract of Q if it can be obtained from Q or one of its inverses by fixing n-m>0 arguments. We prove that if the maximum arity of a permutably irreducible retract of an n-ary quasigroup Q belongs to {3,…,n-3}, then Q is permutably reducible.  相似文献   

18.
We prove that II1 factors M have a unique (up to unitary conjugacy) cross-product type decomposition around “core subfactors” NM satisfying the property HT of [S. Popa, On a class of type II1 factors with Betti numbers invariants, Ann. of Math. (2) 163 (2006) 809-899] and a certain “torsion freeness” condition. In particular, this shows that isomorphism of factors of the form Lαi(Z2)?Fni, i=1,2, for FniSL(2,Z) free groups of rank ni and αj=e2πitj, tjQ, implies n1=n2.  相似文献   

19.
In this paper, based on C3 quartic splines, a semi-discretization method containing two schemes is constructed to solve one-space-dimensional linear hyperbolic equations. It is shown that both schemes are unconditionally stable and their approximation orders are of O(k5+h4) and of O(k7+h4) with k and h being step sizes in time and space, respectively, which are much higher than those of other published schemes. A numerical example is presented and the results are compared with other published numerical results.  相似文献   

20.
The well-known “Bernstein’s weighted problem” deals with the possibility of weighted approximation on the whole real line. In this paper, we show the possibility of k-monotone approximation on the real line with Freud’s weight .  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号