共查询到20条相似文献,搜索用时 31 毫秒
1.
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. 相似文献
2.
The parametric resource allocation problem asks to minimize the sum of separable single-variable convex functions containing a parameter λ, Σ i = 1n (ƒ i( xi + λ gi( xi)), under simple constraints Σ i = 1n xi = M, li≤ xi≤ ui and xi: nonnegative integers for i = 1, 2, …, n, where M is a given positive integer, and li and ui are given lower and upper bounds on xi. This paper presents an efficient algorithm for computing the sequence of all optimal solutions when λ is continuously changed from 0 to ∞. The required time is O( G√ Mlog 2 n + n log n + n log( M/ n)), where G = Σ i = 1n ui − Σ i = 1n li and an evaluation of ƒ i(·) or gi(·) is assumed to be done in constant time. 相似文献
3.
Let G be a graph of order n, and let a and b be integers such that 1 a< b. Let δ( G) be the minimum degree of G. Then we prove that if δ( G)( k−1) a, n( a+ b)( k( a+ b)−2)/ b, and | NG( x1) NG( x2) NG( xk)| an/( a+ b) for any independent subset { x1, x2,…, xk} of V( G), where k2, then G has an [ a, b]-factor. This result is best possible in some sense. 相似文献
4.
We consider the nonlinear parabolic equation ut = ( k( u) ux) x + b( u) x, where u = u( x, t, x ε R1, t > 0; k( u) ≥ 0, b( u) ≥ 0 are continuous functions as u ≥ 0, b (0) = 0; k, b > 0 as u > 0. At t = 0 nonnegative, continuous and bounded initial value is prescribed. The boundary condition u(0, t) = Ψ( t) is supposed to be unbounded as t → +∞. In this paper, sufficient conditions for space localization of unbounded boundary perturbations are found. For instance, we show that nonlinear equation ut = ( unux) x + ( uβ) x, n ≥ 0, β >; n + 1, exhibits the phenomenon of “inner boundedness,” for arbitrary unbounded boundary perturbations. 相似文献
5.
For a connected graph G with n vertices, let {λ 1,λ 2,…,λ r} be the set of distinct positive eigenvalues of the Laplacian matrix of G. The Hoffman number μ( G) of G is defined by μ( G)=λ 1λ 2…λ r/ n. In this paper, we study some properties and applications of the Hoffman number. 相似文献
6.
Let G be a metrizable topological group. Denote by itb( G) the smallest cardinality of a cover of G by totally bounded subsets of G. A group G is defined to be σ -bounded if itb( G) 0. The group G is called o-bounded if for every sequence ( Un) nω of neighborhoods of the identity in G there exists a sequence ( Fn) nω of finite subsets in G such that G= nωFn· Un; G is called strictly o-bounded (respectively OF- determined) if the second player (respectively one of the players) has a winning strategy in the following game OF: two players, I and II, choose at every step n an open neighborhood Un of the identity in G and a finite subset Fn of G, respectively. The player II wins if G= nωFn· Un. For a second countable group G the following results are proven.
. If G is strictly o-bounded, then itb(G)1 and G is σ-bounded or meager. If the space G is analytic, then the group is OF-determined and satisfies
. G is σ-bounded if it is strictly o-bounded and one of the following conditions holds: (i) G is analytic; (ii)
; (iii) (MA+¬CH) holds; (iv) analytic games are determined; (v) there exists a measurable cardinal. Also we show that under (MA) every non-locally compact Polish Abelian divisible group contains a Baire o-bounded OF-undetermined subgroup. 相似文献
7.
In this paper, we consider the optimal assignments of unions of intervals to the vertices of the compatibility graph G, which arises in connection with frequency assignment and traffic phasing problems. It is shown that the optimal multiple interval phasing numbers θ J≥rx( G) and θ J≥rxN( G), are optimal solutions to linear programming problems whose variables correspond to maximal cliques of G. Efficient algorithms are given for determining the first number, θ J≥rx( G), when G is a chordal graph or a transitively orientable graph. 相似文献
8.
Let G be an infinite locally finite connected graph. We study the reconstructibility of G in relation to the structure of its end set
. We prove that an infinite locally finite connected graph G is reconstructible if there exists a finite family (Ωi)0i (n2) of pairwise finitely separable subsets of
such that, for all x, y, x′, y′ V( G) and every isomorphism f of G−{ x, y} onto G−{ x′, y′} there is a permutation π of {0,…, n−1} such that
for 0 i< n. From this theorem we deduce, as particular consequences, that G is reconstructible if it satisfies one of the following properties: (i) G contains no end-respecting subdivision of the dyadic tree and has at least two ends of maximal order; (ii) the set of thick ends or the one of thin ends of G is finite and of cardinality greater than one. We also prove that if almost all vertices of G are cutvertices, then G is reconstructible if it contains a free end or if it has at least a vertex which is not a cutvertex. 相似文献
9.
Let X be a Banach space, S(X) - x ε X : #x02016; = 1 be the unit sphere of X.The parameter, modulus of W*-convexity, W*(ε) = inf <( x − y)/2, fx> : x, y S(X), x − y ≥ ε, fx Δ x , where 0 ≤ ε ≤ 2 and Δ x S(X*) be the set of norm 1 supporting functionals of S(X) at x, is investigated_ The relationship among uniform nonsquareness, uniform normal structure and the parameter W*(ε) are studied, and a known result is improved. The main result is that for a Banach space X, if there is ε, where 0 < ε < 1/2, such that W*(1 + ε) > ε/2 where W*(1 + ε) = lim →ε W* (1 + ), then X has normal structure. 相似文献
10.
A (finite or infinite) graph G is strongly dismantlable if its vertices can be linearly ordered x0,…, x so that, for each ordinal β < , there exists a strictly increasing finite sequence ( ij) 0 j n of ordinals such that i0 = β, in = and xij+1 is adjacent with xij and with all neighbors of xij in the subgraph of G induced by { xy: β γ }. We show that the Helly number for the geodesic convexity of such a graph equals its clique number. This generalizes a result of Bandelt and Mulder (1990) for dismantlable graphs. We also get an analogous equality dealing with infinite families of convex sets. 相似文献
11.
Let G be a plane graph, and let χ k( G) be the minimum number of colors to color the vertices of G so that every two of them which lie in the boundary of the same face of the size at most k, receive different colors. In 1966, Ore and Plummer proved that χ k( G)2 k for any k3. It is also known that χ 3( G)4 (Appel and Haken, 1976) and χ 4( G)6 (Borodin, 1984). The result in the present paper is: χ 5( G)9, χ 6( G)11, χ 7( G)12, and χ k( G)2 k − 3 if k8. 相似文献
12.
We study the problem of designing fault-tolerant routings with small routing tables for a k-connected network of n processors in the surviving route graph model. The surviving route graph R( G,ρ)/ F for a graph G, a routing ρ and a set of faults F is a directed graph consisting of nonfaulty nodes of G with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerance measures for the graph G and the routing ρ and it is denoted by D( R( G,ρ)/ F). We want to reduce the total number of routes defined in the routing, and the maximum of the number of routes defined for a node (called route degree) as least as possible. In this paper, we show that we can construct a routing λ for every n-node k-connected graph such that n2 k2, in which the route degree is
, the total number of routes is O( k2n) and D( R( G,λ)/ F)3 for any fault set F (| F|< k). In particular, in the case that k=2 we can construct a routing λ′ for every biconnected graph in which the route degree is
, the total number of routes is O( n) and D( R( G,λ′)/{ f})3 for any fault f. We also show that we can construct a routing ρ 1 for every n-node biconnected graph, in which the total number of routes is O( n) and D( R( G,ρ 1)/{ f})2 for any fault f, and a routing ρ 2 (using ρ 1) for every n-node biconnected graph, in which the route degree is
, the total number of routes is
and D( R( G,ρ 2)/{ f})2 for any fault f. 相似文献
13.
Let A be a positive definite, symmetric matrix. We wish to determine the largest eigenvalue, λ 1. We consider the power method, i.e. that of choosing a vector v0 and setting vk = Akv0; then the Rayleigh quotients Rk = ( Avk, vk)/( vk, vk) usually converge to λ 1 as k → ∞ (here ( u, v) denotes their inner product). In this paper we give two methods for determining how close Rk is to λ 1. They are both based on a bound on λ 1 − Rk involving the difference of two consecutive Rayleigh quotients and a quantity ω k. While we do not know how to directly calculate ω k, we can given an algorithm for giving a good upper bound on it, at least with high probability. This leads to an upper bound for λ 1 − Rk which is proportional to (λ 2/λ 1) 2k, which holds with a prescribed probability (the prescribed probability being an arbitrary δ > 0, with the upper bound depending on δ). 相似文献
14.
The problem of building larger graphs with a given graph as an induced subgraph is one which can arise in various applications and in particular can be important when constructing large communications networks from smaller ones. What one can conclude from this paper is that generalized prisms over G may provide an important such construction because the connectivity of the newly created graph is larger than that of the original (connected) graph, regardless of the permutation used. For a graph G with vertices labeled 1,2,…, n and a permutation in Sn, the generalized prisms over G, (G) (also called a permutation graph), consists of two copies of G, say Gx and Gy, along with the edges (xi, y(i), for 1≤i≤n. The purpose of this paper is to examine the connectivity of generalized prisms over G. In particular, upper and lower bounds are found. Also, the connectivity and edge-connectivity are determined for generalized prisms over trees, cycles, wheels, n-cubes, complete graphs, and complete bipartite graphs. Finally, the connectivity of the generalized prism over G, (G), is determined for all in the automorphism group of G. 相似文献
15.
We present a characterization of those Euclidean distance matrices (EDMs) D which can be expressed as D=λ( E− C) for some nonnegative scalar λ and some correlation matrix C, where E is the matrix of all ones. This shows that the cones where
is the elliptope (set of correlation matrices) and
is the (closed convex) cone of EDMs. The characterization is given using the Gale transform of the points generating D. We also show that given points
, for any scalars λ1,λ2,…,λn such that we have ∑j=1nλjpi−pj2= forall i=1,…,n, for some scalar independent of i. 相似文献
16.
For an integer n3, the crown Sn0 is defined to be the graph with vertex set { x0, x1,…, xn−1, y0, y1,…, yn−1} and edge set { xiyj: 0 i, jn−1, i≠ j}. In this paper we give some sufficient conditions for the edge decomposition of the crown into isomorphic cycles. 相似文献
17.
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. 相似文献
18.
A construction is given for a ( p2a( p+1), p2, p2a+1( p+1), p2a+1, p2a( p+1)) ( p a prime) divisible difference set in the group H× Z2pa+1 where H is any abelian group of order p+1. This can be used to generate a symmetric semi-regular divisible design; this is a new set of parameters for λ 1≠0, and those are fairly rare. We also give a construction for a ( pa−1+ pa−2+…+ p+2, pa+2, pa( pa+ pa−1+…+ p+1), pa( pa−1+…+ p+1), pa−1( pa+…+ p2+2)) divisible difference set in the group H× Zp2× Zap. This is another new set of parameters, and it corresponds to a symmetric regular divisible design. For p=2, these parameters have λ 1=λ 2, and this corresponds to the parameters for the ordinary Menon difference sets. 相似文献
19.
A bisequence of complex numbers {μ n} −∞∞ determines a strong moment functional
satisfying L[ xn] = μ n. If
is positive-definite on a bounded interval ( a, b) R{0}, then
has an integral representation
, n=0, ±1, ±2,…, and quadrature rules { wni, xni} exist such that μ k = ∑ i=innsnikwni. This paper is concerned with establishing certain extremal properties of the weights wni and using these properties to obtain maximal mass results satisfied by distributions ψ( x) representing
when only a finite bisequence of moments {μ k} k=−nn−1 is given. 相似文献
20.
The chromatic difference sequence cds( G) of a graph G with chromatic number n is defined by cds( G) = ( a(1), a(2),…, a( n)) if the sum of a(1), a(2),…, a( t) is the maximum number of vertices in an induced t-colorable subgraph of G for t = 1, 2,…, n. The Cartesian product of two graphs G and H, denoted by G□ H, has the vertex set V( G□ H = V( G) x V( H) and its edge set is given by ( x1, y1)( x2, y2) ε E( G□ H) if either x1 = x2 and y1 y2 ε E( H) or y1 = y2 and x1x2 ε E( G). We obtained four main results: the cds of the product of bipartite graphs, the cds of the product of graphs with cds being nondrop flat and first-drop flat, the non-increasing theorem for powers of graphs and cds of powers of circulant graphs. 相似文献
|