共查询到20条相似文献,搜索用时 187 毫秒
1.
Gould et al. (Combinatorics, Graph Theory and Algorithms, Vol. 1, 1999, pp. 387–400) considered a variation of the classical Turán-type extremal problems as follows: For a given graph H, determine the smallest even integer σ( H, n) such that every n-term graphic sequence π=( d1, d2,…, dn) with term sum σ( π)= d1+ d2++ dnσ( H, n) has a realization G containing H as a subgraph. In this paper, for given integers k and ℓ, ℓ7 and 3 kℓ, we completely determine the smallest even integer σ( kCℓ, n) such that each n-term graphic sequence π=( d1, d2,…, dn) with term sum σ( π)= d1+ d2++ dnσ( kCℓ, n) has a realization G containing a cycle of length r for each r, krℓ. 相似文献
2.
A graph G is maximal IM-unextendable if G is not induced matching extendable and, for every two nonadjacent vertices x and y, G+ xy is induced matching extendable. We show in this paper that a graph G is maximal IM-unextendable if and only if G is isomorphic to Mr( Ks( Kn1Kn2Knt)), where Mr is an induced matching of size r, r1, t= s+2, and each ni is odd. 相似文献
3.
The Ramsey number r( H, Kn) is the smallest integer N so that each graph on N vertices that fails to contain H as a subgraph has independence number at least n. It is shown that r( K2,m, Kn)( m−1+o(1))( n/log n) 2 and r( C2m, Kn) c( n/log n) m/(m−1) for m fixed and n→∞. Also r( K2,n, Kn)=Θ( n3/log 2 n) and
. 相似文献
4.
Let Z denote the set of all integers. The integral sum graph of a finite subset S of Z is the graph ( S, E) with vertex set S and edge set E such that for u, vS, uvE if and only if u+ vS. A graph G is called an integral sum graph if it is isomorphic to the integral sum graph of some finite subset S of Z. The integral sum number of a given graph G, denoted by ζ( G), is the smallest number of isolated vertices which when added to G result in an integral sum graph. Let x denote the least integer not less than the real x. In this paper, we (i) determine the value of ζ( Kn− E( Kr)) for r2 n/3−1, (ii) obtain a lower bound for ζ( Kn− E( Kr)) when 2 r<2 n/3−1 and n5, showing by construction that the bound is sharp when r=2, and (iii) determine the value of ζ( Kr,r) for r2. These results provide partial solutions to two problems posed by Harary (Discrete Math. 124 (1994) 101–108). Finally, we furnish a counterexample to a result on the sum number of Kr,s given by Hartsfiedl and Smyth (Graphs and Matrices, R. Rees (Ed.), Marcel, Dekker, New York, 1992, pp. 205–211). 相似文献
5.
A graph G with n vertices is said to be embeddable (in its complement) if there is an automorphism φ of Kn such that E( G) ∩ E(φ( G))=. It is known that all trees T with n (≥2) vertices and T K1,n−1 are embeddable. We say that G is 1-embeddable if, for every edge e, there is an automorphism φ of Kn such that E( G) ∩ E(φ( G))={ e};and that it is 2-embeddable if,for every pair e1, e2 of edges, there is an automorphism φ of Kn such that E( G) ∩ E(φ( G))={ e1, e2}. We prove here that all trees with n (3) vertices are 1-embeddable; and that all trees T with n (4) vertices and T K1,n−1 are 2-embeddable. In a certain sense, this result is sharp. 相似文献
6.
Let X1, X2,…be identically distributed random variables from an unknown continuous distribution. Further let Ir(1), Ir(2),…be a sequence of indicator functions defined on X1, X2,…by Ir( k) = 0 if k < r, Ir( k) = 1 if Xk is a r-record AND = 0 otherwise. Suppose that we observe X1, X2,… at times T1 < T2 <… where the Tk's are realisations of some regular counting process ( N(τ)) defined on the positive half-line. Having observed [0, τ], say, the problem is to predict the future behaviour of the counting processes ( Rr(τ, s)) sτ = # r-records in [τ, s]. More specifically the objective of this paper is to show that these processes can be (inhomogeneous) Poisson processes even if ( N(τ)) τ0 has dependent increments. The strong link between optimal selection and optimal stopping of record sequences or record processes, perhaps not fully recognized so far, is pointed out in this paper. It is shown to lead to a unification of the treatment of problems which, at first sight, are rather different. Moreover the stopping of record processes in continuous time can lead to rigorous and elegant solutions in cases where dynamic programming is bound to fail. Several examples will be given to facilitate a comparison with other methods. 相似文献
7.
An ( r, n)-split coloring of a complete graph is an edge coloring with r colors under which the vertex set is partitionable into r parts so that for each i, part i does not contain Kn in color i. This generalizes the notion of split graphs which correspond to (2, 2)-split colorings. The smallest N for which the complete graph KN has a coloring which is not ( r, n)-split is denoted by ƒ r( n). Balanced ( r, n)-colorings are defined as edge r-colorings of KN such that every subset of [ N/ r] vertices contains a monochromatic Kn in all colors. Then gr( n) is defined as the smallest N such that KN has a balanced ( r, n)-coloring. The definitions imply that fr( n) gr( n). The paper gives estimates and exact values of these functions for various choices of parameters. 相似文献
8.
A mapping ƒ : n=1∞In → I is called a bag mapping having the self-identity if for every ( x1,…, xn) ε i=1∞In we have (1) ƒ( x1,…, xn) = ƒ( xi1,…, xin) for any arrangement ( i1,…, in) of {1,…, n}; monotonic; (3) ƒ( x1,…, xn, ƒ( x1,…, xn)) = ƒ( x1,…, xn). Let {ω i,n : I = 1,…, n; n = 1,2,…} be a family of non-negative real numbers satisfying Σ i=1nω i,n = 1 for every n. Then one calls the mapping ƒ : i=1∞In → I defined as follows an OWA bag mapping: for every ( x1,…, xn) ε i=1∞In, ƒ( x1,…, xn) = Σ i=1nω i,nyi, where yi is the it largest element in the set { x1,…, xn}. In this paper, we give a sufficient and necessary condition for an OWA bag mapping having the self-identity. 相似文献
9.
This paper considers a class of nonlinear difference equations Δ3yn + ƒ(n, yn, yn−r) = 0, n N (n0) . A necessary and sufficient condition for the existence of a bounded nonoscillatory solution is given. 相似文献
10.
Let I be a compact interval of real axis R, and(I, H) be the metric space of all nonempty closed subintervals of I with the Hausdorff metric H and f : I → I be a continuous multi-valued map. Assume that Pn =(x_0, x_1,..., xn) is a return tra jectory of f and that p ∈ [min Pn, max Pn] with p ∈ f(p). In this paper, we show that if there exist k(≥ 1) centripetal point pairs of f(relative to p)in {(x_i; x_i+1) : 0 ≤ i ≤ n-1} and n = sk + r(0 ≤ r ≤ k-1), then f has an R-periodic orbit, where R = s + 1 if s is even, and R = s if s is odd and r = 0, and R = s + 2 if s is odd and r 0. Besides,we also study stability of periodic orbits of continuous multi-valued maps from I to I. 相似文献
11.
A cover (bipartite) of a graph G is a family of complete bipartite subgraphs of G whose edges cover G's edges. G's bipartite dimension d(G) is the minimum cardinality of a cover, and its bipartite degree η(G) is the minimum over all covers of the maximum number of covering members incident to a vertex. We prove that d( G) equals the Boolean interval dimension of the irreflexive complement of G, identify the 21 minimal forbidden induced subgraphs for d 2, and investigate the forbidden graphs for d n that have the fewest vertices. We note that for complete graphs, d( Kn) = [log 2n], η( Kn) = d( Kn) for n 16, and η( Kn) is unbounded. The list of minimal forbidden induced subgraphs for η 2 is infinite. We identify two infinite families in this list along with all members that have fewer than seven vertices. 相似文献
12.
For a 1-dependent stationary sequence { Xn} we first show that if u satisfies p1= p1( u)= P( X1> u)0.025 and n>3 is such that 88 np131, then P{max(X1,…,Xn)u}=ν·μn+O{p13(88n(1+124np13)+561)}, n>3, where ν=1−p2+2p3−3p4+p12+6p22−6p1p2,μ=(1+p1−p2+p3−p4+2p12+3p22−5p1p2)−1 with pk=pk(u)=P{min(X1,…,Xk)>u}, k1 and From this result we deduce, for a stationary T-dependent process with a.s. continuous path { Ys}, a similar, in terms of P{max 0skTYs< u}, k=1,2 formula for P{max 0stYsu}, t>3 T and apply this formula to the process Ys= W( s+1)− W( s), s0, where { W( s)} is the Wiener process. We then obtain numerical estimations of the above probabilities. 相似文献
13.
We consider the following model Hr( n, p) of random r-uniform hypergraphs. The vertex set consists of two disjoint subsets V of size | V | = n and U of size | U | = ( r − 1) n. Each r-subset of V × ( r−1U) is chosen to be an edge of H ε Hr( n, p) with probability p = p( n), all choices being independent. It is shown that for every 0 < < 1 if P = ( C ln n)/ nr−1 with C = C() sufficiently large, then almost surely every subset V1 V of size | V1 | = (1 − ) n is matchable, that is, there exists a matching M in H such that every vertex of V1 is contained in some edge of M. 相似文献
14.
A random graph Gn( x) is constructed on independent random points U1,…, Un distributed uniformly on [0,1] d, d1, in which two distinct such points are joined by an edge if the l∞-distance between them is at most some prescribed value 0< x<1. The connectivity distance cn, the smallest x for which Gn( x) is connected, is shown to satisfy For d2, the random graph Gn( x) behaves like a d-dimensional version of the random graphs of Erdös and Rényi, despite the fact that its edges are not independent: cn/ dn→1, a.s., as n→∞, where dn is the largest nearest-neighbor link, the smallest x for which Gn( x) has no isolated vertices. 相似文献
15.
Let sk( n) be the largest integer such that every n-point interval order with no antichain of more than k points includes an sk( n)-point semiorder. When k = 1, s1( n) = n since all interval orders with no two-point antichains are chains. Given ( c1,..., c5) = (1, 2, 3, 4), it is shown that s2( n) = cn for n 4, s3( n) = cn for n 5, and for all positive n, s2 ( n+4) = s2( n)+3, s3( n+5) = s3( n)+3. Hence s2 has a repeating pattern of length 4 [1, 2, 3, 3; 4, 5, 6, 6; 7, 8, 9, 9;...], and s3 has a repeating pattern of length 5 [1, 2, 3, 3, 4; 4, 5, 6, 6, 7; 7, 8, 9, 9, 10;...]. Let s(n) be the largest integer such that every n-point interval order includes an s(n)-point semiorder. It was proved previously that
for even n from 4 to 14, and that s(17) = 9. We prove here that s(15) = s(16) = 9, so that s begins 1, 2, 3, 3, 4, 4,..., 8, 8, 9, 9, 9. Since s(n)/n→0, s cannot have a repeating pattern. 相似文献
16.
Let B be a separable Banach space. The following is one of the results proved in this paper. The Banach space B is of cotype p if and only if 1. dn, n 1, has no subsequence converging in probability, and 2. ∑n 1|an|p < ∞ whenever ∑n 1andn converges almost surely are equivalent for every sequence dn, n 1, of symmetric independent random elements taking values in B.
Author Keywords: Bounded in probability; convergence in probability; cotype; uniform tightness condition 相似文献
17.
We give criterions for a flat portion to exist on the boundary of the numerical range of a matrix. A special type of Teoplitz matrices with flat portions on the boundary of its numerical range are constructed. We show that there exist 2 × 2 nilpotent matrices A1, A2, an n × n nilpotent Toeplitz matrix Nn, and an n × n cyclic permutation matrix Sn( s) such that the numbers of flat portions on the boundaries of W( A1⊕ Nn) and W( A2⊕ Sn( s)) are, respectively, 2( n - 2) and 2 n. 相似文献
18.
Suppose G is a graph. The chromatic Ramsey number rc( G) of G is the least integer m such that there exists a graph F of chromatic number m for which the following is true: for any 2-colouring of the edges of F there is a monochromatic subgraph isomorphic to G. Let Mn = min[ rc( G): χ( G) = n]. It was conjectured by Burr et al. (1976) that Mn = ( n − 1) 2 + 1. This conjecture has been confirmed previously for n 4. In this paper, we shall prove that the conjecture is true for n = 5. We shall also improve the upper bounds for M6 and M7. 相似文献
19.
We have considered the problem of the weak convergence, as tends to zero, of the multiple integral processes in the space
, where fL2([0, T] n) is a given function, and {η ( t)} >0 is a family of stochastic processes with absolutely continuous paths that converges weakly to the Brownian motion. In view of the known results when n2 and f( t1,…, tn)=1 {t1<t2<<tn}, we cannot expect that these multiple integrals converge to the multiple Itô–Wiener integral of f, because the quadratic variations of the η are null. We have obtained the existence of the limit for any {η }, when f is given by a multimeasure, and under some conditions on {η } when f is a continuous function and when f( t1,…, tn)= f1( t1) fn( tn)1 {t1<t2<<tn}, with fiL2([0, T]) for any i=1,…, n. In all these cases the limit process is the multiple Stratonovich integral of the function f. 相似文献
20.
If
are maximal nests on a finite-dimensional Hilbert space H, the dimension of the intersection of the corresponding nest algebras is at least dim H. On the other hand, there are three maximal nests whose nest algebras intersect in the scalar operators. The dimension of the intersection of two nest algebras (corresponding to maximal nests) can be of any integer value from n to n( n+1)/2, where n=dim H. For any two maximal nests
there exists a basis { f1, f2,…, fn} of H and a permutation π such that
and
where Mi= span{ f1, f2,…, fi} and Ni= span{ fπ(1), fπ(2),…, fπ(i)}. The intersection of the corresponding nest algebras has minimum dimension, namely dim H, precisely when π( j)= n− j+1,1 jn. Those algebras which are upper-triangular matrix incidence algebras, relative to some basis, can be characterised as intersections of certain nest algebras. 相似文献
|