首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
Let G=(V,E) be a graph and let r≥1 be an integer. For a set DV, define Nr[x]={yV:d(x,y)≤r} and Dr(x)=Nr[x]∩D, where d(x,y) denotes the number of edges in any shortest path between x and y. D is known as an r-identifying code (r-locating-dominating set, respectively), if for all vertices xV (xV?D, respectively), Dr(x) are all nonempty and different. Roberts and Roberts [D.L. Roberts, F.S. Roberts, Locating sensors in paths and cycles: the case of 2-identifying codes, European Journal of Combinatorics 29 (2008) 72-82] provided complete results for the paths and cycles when r=2. In this paper, we provide results for a remaining open case in cycles and complete results in paths for r-identifying codes; we also give complete results for 2-locating-dominating sets in cycles, which completes the results of Bertrand et al. [N. Bertrand, I. Charon, O. Hudry, A. Lobstein, Identifying and locating-dominating codes on chains and cycles, European Journal of Combinatorics 25 (2004) 969-987].  相似文献   

2.
We investigate the class R∞,s of rapidly varying sequences from different points of view. It is shown: (1) a sequence (cn)nN of positive real numbers is rapidly varying if and only if the corresponding function xc[x], x?1, is rapidly varying; (2) the class R∞,s satisfies some selection properties, as well as game-theoretical and Ramsey-theoretical conditions.  相似文献   

3.
In this paper we introduce a convergence concept for closed convex subsets of a finite-dimensional normed vector space. This convergence is called C-convergence. It is defined by appropriate notions of upper and lower limits. We compare this convergence with the well-known Painlevé-Kuratowski convergence and with scalar convergence. In fact, we show that a sequence (An)nNC-converges to A if and only if the corresponding support functions converge pointwise, except at relative boundary points of the domain of the support function of A, to the support function of A.  相似文献   

4.
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.  相似文献   

5.
Let r?2 be an integer. A real number α∈[0,1) is a jump for r if for any ε>0 and any integer m?r, any r-uniform graph with n>n0(ε,m) vertices and density at least α+ε contains a subgraph with m vertices and density at least α+c, where c=c(α)>0 does not depend on ε and m. A result of Erd?s, Stone and Simonovits implies that every α∈[0,1) is a jump for r=2. Erd?s asked whether the same is true for r?3. Frankl and Rödl gave a negative answer by showing an infinite sequence of non-jumping numbers for every r?3. However, there are a lot of unknowns on determining whether or not a number is a jump for r?3. In this paper, we find two infinite sequences of non-jumping numbers for r=4, and extend one of the results to every r?4. Our approach is still based on the approach developed by Frankl and Rödl.  相似文献   

6.
Let m(n,k,r,t) be the maximum size of satisfying |F1∩?∩Fr|≥t for all F1,…,FrF. We prove that for every p∈(0,1) there is some r0 such that, for all r>r0 and all t with 1≤t≤⌊(p1−rp)/(1−p)⌋−r, there exists n0 so that if n>n0 and p=k/n, then . The upper bound for t is tight for fixed p and r.  相似文献   

7.
Maria Monks 《Discrete Mathematics》2009,309(16):5196-1883
All continuous endomorphisms f of the shift dynamical system S on the 2-adic integers Z2 are induced by some , where n is a positive integer, Bn is the set of n-blocks over {0, 1}, and f(x)=y0y1y2… where for all iN, yi=f(xixi+1xi+n−1). Define D:Z2Z2 to be the endomorphism of S induced by the map {(00,0),(01,1),(10,1),(11,0)} and V:Z2Z2 by V(x)=−1−x. We prove that D, V°D, S, and V°S are conjugate to S and are the only continuous endomorphisms of S whose parity vector function is solenoidal. We investigate the properties of D as a dynamical system, and use D to construct a conjugacy from the 3x+1 function T:Z2Z2 to a parity-neutral dynamical system. We also construct a conjugacy R from D to T. We apply these results to establish that, in order to prove the 3x+1 conjecture, it suffices to show that for any mZ+, there exists some nN such that R−1(m) has binary representation of the form or .  相似文献   

8.
Let X be a Banach space and C a bounded, closed, convex subset of X. C is said to have the weak-approximate fixed point property if for any norm-continuous mapping , there exists a sequence {xn} in C such that (xnfn(xn)) converges to 0 weakly. It is known that every infinite-dimensional Banach space with the Schur property does not have the weak-approximate fixed point property. In this article, we show that every Asplund space has the weak-approximate fixed point property. Applications to the asymptotic fixed point theory are given.  相似文献   

9.
Let D be an edge-coloured digraph, V(D) will denote the set of vertices of D; a set NV(D) is said to be a kernel by monochromatic paths of D if it satisfies the following two conditions: For every pair of different vertices u,vN there is no monochromatic directed path between them and; for every vertex xV(D)−N there is a vertex yN such that there is an xy-monochromatic directed path.In this paper we consider some operations on edge-coloured digraphs, and some sufficient conditions for the existence or uniqueness of kernels by monochromatic paths of edge-coloured digraphs formed by these operations from another edge-coloured digraphs.  相似文献   

10.
Let Y be a subset of real numbers. A Y-dominating function of a graph G=(V,E) is a function f:VY such that for all vertices vV, where NG[v]={v}∪{u|(u,v)∈E}. Let for any subset S of V and let f(V) be the weight of f. The Y-domination problem is to find a Y-dominating function of minimum weight for a graph G=(V,E). In this paper, we study the variations of Y-domination such as {k}-domination, k-tuple domination, signed domination, and minus domination for some classes of graphs. We give formulas to compute the {k}-domination, k-tuple domination, signed domination, and minus domination numbers of paths, cycles, n-fans, n-wheels, n-pans, and n-suns. Besides, we present a unified approach to these four problems on strongly chordal graphs. Notice that trees, block graphs, interval graphs, and directed path graphs are subclasses of strongly chordal graphs. This paper also gives complexity results for the problems on doubly chordal graphs, dually chordal graphs, bipartite planar graphs, chordal bipartite graphs, and planar graphs.  相似文献   

11.
Motivated by the discovery that the eighth root of the theta series of the E8 lattice and the 24th root of the theta series of the Leech lattice both have integer coefficients, we investigate the question of when an arbitrary element fR (where R=1+xZ?x?) can be written as f=gn for gR, n?2. Let Pn:={gn|gR} and let . We show among other things that (i) for fR, fPnf (mod μn)∈Pn, and (ii) if fPn, there is a unique gPn with coefficients mod μn/n such that fgn (mod μn). In particular, if f≡1 (mod μn) then fPn. The latter assertion implies that the theta series of any extremal even unimodular lattice in Rn (e.g. E8 in R8) is in Pn if n is of the form i2j3k5 (i?3). There do not seem to be any exact analogues for codes, although we show that the weight enumerator of the rth order Reed-Muller code of length m2 is in Pr2 (and similarly that the theta series of the Barnes-Wall lattice BWm2 is in Pm2). We give a number of other results and conjectures, and establish a conjecture of Paul D. Hanna that there is a unique element fPn (n?2) with coefficients restricted to the set {1,2,…,n}.  相似文献   

12.
A graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. For a nonnegative integer k, a graph G is called a k-edge-deletable IM-extendable graph, if, for every FE(G) with |F|=k, GF is IM-extendable. In this paper, we characterize the k-edge-deletable IM-extendable graphs with minimum number of edges. We show that, for a positive integer k, if G is ak-edge-deletable IM-extendable graph on 2n vertices, then |E(G)|≥(k+2)n; furthermore, the equality holds if and only if either GKk+2,k+2, or k=4r−2 for some integer r≥3 and GC5[N2r], where N2r is the empty graph on 2r vertices and C5[N2r] is the graph obtained from C5 by replacing each vertex with a graph isomorphic to N2r.  相似文献   

13.
A p-adic Schrödinger-type operator Dα+VY is studied. Dα (α>0) is the operator of fractional differentiation and (bijC) is a singular potential containing the Dirac delta functions δx concentrated on a set of points Y={x1,…,xn} of the field of p-adic numbers Qp. It is shown that such a problem is well posed for α>1/2 and the singular perturbation VY is form-bounded for α>1. In the latter case, the spectral analysis of η-self-adjoint operator realizations of Dα+VY in L2(Qp) is carried out.  相似文献   

14.
Let G be a second-countable locally-compact Hausdorff groupoid with a Haar system, and let {xn} be a sequence in the unit space G(0) of G. We show that the notions of strength of convergence of {xn} in the orbit space G(0)/G and measure-theoretic accumulation along the orbits are equivalent ways of realising multiplicity numbers associated to a sequence of induced representation of the groupoid C?-algebra.  相似文献   

15.
In 1967 Komlós proved that for any sequence n{fn} in L1(μ), with ‖fn‖?M<∞ (where μ is a probability measure), there exists a subsequence n{gn} of n{fn} and a function gL1(μ) such that for any further subsequence n{hn} of n{gn},
  相似文献   

16.
Let D be a directed graph; the (l,ω)-Independence Number of graph D, denoted by αl,ω(D), is an important performance parameter for interconnection networks. De Bruijn networks and Kautz networks, denoted by B(d,n) and K(d,n) respectively, are versatile and efficient topological structures of interconnection networks. For l=1,2,…,n, this paper shows that αl,d−1(B(d,n))=dn,αl,d−1(K(d,n))=αl,d(K(d,n))=dn+dn−1 if d≥3 and nd−2. In particular, the paper shows the exact value of the Independence Number for B(d,1) and B(d,2) for any d. For the generalized situation, the paper obtains a lower bound αl,d−1(B(d,n))≥d2 if n≥3 and d≥5.  相似文献   

17.
A nonincreasing sequence of nonnegative integers π=(d1,d2,…,dn) is graphic if there is a (simple) graph G of order n having degree sequence π. In this case, G is said to realizeπ. For a given graph H, a graphic sequence π is potentiallyH-graphic if there is some realization of π containing H as a (weak) subgraph. Let σ(π) denote the sum of the terms of π. For a graph H and nZ+, σ(H,n) is defined as the smallest even integer m so that every n-term graphic sequence π with σ(π)≥m is potentially H-graphic. Let denote the complete t partite graph such that each partite set has exactly s vertices. We show that and obtain the exact value of σ(Kj+Ks,s,n) for n sufficiently large. Consequently, we obtain the exact value of for n sufficiently large.  相似文献   

18.
Let G be a graph and d(u) denote the degree of a vertex u in G. The zeroth-order general Randi? index 0Rα(G) of the graph G is defined as ∑uV(G)d(u)α, where the summation goes over all vertices of G and α is an arbitrary real number. In this paper we correct the proof of the main Theorem 3.5 of the paper by Hu et al. [Y. Hu, X. Li, Y. Shi, T. Xu, Connected (n,m)-graphs with minimum and maximum zeroth-order general Randi? index, Discrete Appl. Math. 155 (8) (2007) 1044-1054] and give a more general Theorem. We finally characterize 1 for α<0 the connected G(n,m)-graphs with maximum value 0Rα(G(n,m)), where G(n,m) is a simple connected graph with n vertices and m edges.  相似文献   

19.
Given a graph G, a proper labelingf of G is a one-to-one function from V(G) onto {1,2,…,|V(G)|}. For a proper labeling f of G, the profile widthwf(v) of a vertex v is the minimum value of f(v)−f(x), where x belongs to the closed neighborhood of v. The profile of a proper labelingfofG, denoted by Pf(G), is the sum of all the wf(v), where vV(G). The profile ofG is the minimum value of Pf(G), where f runs over all proper labeling of G. In this paper, we show that if the vertices of a graph G can be ordered to satisfy a special neighborhood property, then so can the graph G×Qn. This can be used to determine the profile of Qn and Km×Qn.  相似文献   

20.
Let X be a Banach space and Z a nonempty subset of X. Let J:ZR be a lower semicontinuous function bounded from below and p?1. This paper is concerned with the perturbed optimization problem of finding z0Z such that ‖xz0p+J(z0)=infzZ{‖xzp+J(z)}, which is denoted by minJ(x,Z). The notions of the J-strictly convex with respect to Z and of the Kadec with respect to Z are introduced and used in the present paper. It is proved that if X is a Kadec Banach space with respect to Z and Z is a closed relatively boundedly weakly compact subset, then the set of all xX for which every minimizing sequence of the problem minJ(x,Z) has a converging subsequence is a dense Gδ-subset of X?Z0, where Z0 is the set of all points zZ such that z is a solution of the problem minJ(z,Z). If additionally p>1 and X is J-strictly convex with respect to Z, then the set of all xX for which the problem minJ(x,Z) is well-posed is a dense Gδ-subset of X?Z0.  相似文献   

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

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