首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
In this paper we present two upper bounds on the length of a shortest closed geodesic on compact Riemannian manifolds. The first upper bound depends on an upper bound on sectional curvature and an upper bound on the volume of the manifold. The second upper bound will be given in terms of a lower bound on sectional curvature, an upper bound on the diameter and a lower bound on the volume.The related questions that will also be studied are the following: given a contractible k-dimensional sphere in M n , how “fast” can this sphere be contracted to a point, if π i (M n )={0} for 1≤i<k. That is, what is the maximal length of the trajectory described by a point of a sphere under an “optimal” homotopy? Also, what is the “size” of the smallest non-contractible k-dimensional sphere in a (k-1)-connected manifold M n providing that M n is not k-connected?  相似文献   

2.
We improve upon the best known upper and lower bounds on the sizes of minimal feedback vertex sets in butterflies. Also, we construct new feedback vertex sets in grids so that for a large number of pairs (n,m), the size of our feedback vertex set in the grid Mn,m matches the best known lower bound, and for all other pairs it differs from this lower bound by at most 2.  相似文献   

3.
A Bethe tree Bd,k is a rooted unweighted of k levels in which the root vertex has degree equal to d, the vertices at level j(2?j?k-1) have degree equal to (d+1) and the vertices at level k are the pendant vertices. In this paper, we first derive an explicit formula for the eigenvalues of the adjacency matrix of Bd,k. Moreover, we give the corresponding multiplicities. Next, we derive an explicit formula for the simple nonzero eigenvalues, among them the largest eigenvalue, of the Laplacian matrix of Bd,k. Finally, we obtain upper bounds on the largest eigenvalue of the adjacency matrix and of the Laplacian matrix of any tree T. These upper bounds are given in terms of the largest vertex degree and the radius of T, and they are attained if and only if T is a Bethe tree.  相似文献   

4.
In this paper we give some lower and upper bounds for the smallest length n(k, d) of a binary linear code with dimension k and minimum distance d. The lower bounds improve the known ones for small d. In the last section we summarize what we know about n(8, d).  相似文献   

5.
In this paper, we derive an explicit expression for the parameter sequences of a chain sequence in terms of the corresponding orthogonal polynomials and their associated polynomials. We use this to study the orthogonal polynomials Kn(λ,M,k) associated with the probability measure dφ(λ,M,k;x), which is the Gegenbauer measure of parameter λ+1 with two additional mass points at ±k. When k=1 we obtain information on the polynomials Kn(λ,M) which are the symmetric Koornwinder polynomials. Monotonicity properties of the zeros of Kn(λ,M,k) in relation to M and k are also given.  相似文献   

6.
J. Conde 《Discrete Mathematics》2009,309(10):3166-1344
In the context of the degree/diameter problem, the ‘defect’ of a graph represents the difference between the corresponding Moore bound and its order. Thus, a graph with maximum degree d and diameter two has defect two if its order is n=d2−1. Only four extremal graphs of this type, referred to as (d,2,2)-graphs, are known at present: two of degree d=3 and one of degree d=4 and 5, respectively. In this paper we prove, by using algebraic and spectral techniques, that for all values of the degree d within a certain range, (d,2,2)-graphs do not exist.The enumeration of (d,2,2)-graphs is equivalent to the search of binary symmetric matrices A fulfilling that AJn=dJn and A2+A+(1−d)In=Jn+B, where Jn denotes the all-one matrix and B is the adjacency matrix of a union of graph cycles. In order to get the factorization of the characteristic polynomial of A in Q[x], we consider the polynomials Fi,d(x)=fi(x2+x+1−d), where fi(x) denotes the minimal polynomial of the Gauss period , being ζi a primitive ith root of unity. We formulate a conjecture on the irreducibility of Fi,d(x) in Q[x] and we show that its proof would imply the nonexistence of (d,2,2)-graphs for any degree d>5.  相似文献   

7.
A subset X in the d-dimensional Euclidean space is called a k-distance set if there are exactly k distinct distances between two distinct points in X and a subset X is called a locally k-distance set if for any point x in X, there are at most k distinct distances between x and other points in X.Delsarte, Goethals, and Seidel gave the Fisher type upper bound for the cardinalities of k-distance sets on a sphere in 1977. In the same way, we are able to give the same bound for locally k-distance sets on a sphere. In the first part of this paper, we prove that if X is a locally k-distance set attaining the Fisher type upper bound, then determining a weight function w, (X,w) is a tight weighted spherical 2k-design. This result implies that locally k-distance sets attaining the Fisher type upper bound are k-distance sets. In the second part, we give a new absolute bound for the cardinalities of k-distance sets on a sphere. This upper bound is useful for k-distance sets for which the linear programming bound is not applicable. In the third part, we discuss about locally two-distance sets in Euclidean spaces. We give an upper bound for the cardinalities of locally two-distance sets in Euclidean spaces. Moreover, we prove that the existence of a spherical two-distance set in (d−1)-space which attains the Fisher type upper bound is equivalent to the existence of a locally two-distance set but not a two-distance set in d-space with more than d(d+1)/2 points. We also classify optimal (largest possible) locally two-distance sets for dimensions less than eight. In addition, we determine the maximum cardinalities of locally two-distance sets on a sphere for dimensions less than forty.  相似文献   

8.
It is known that for each d there exists a graph of diameter two and maximum degree d which has at least ⌈(d/2)⌉ ⌈(d + 2)/2⌉ vertices. In contrast with this, we prove that for every surface S there is a constant ds such that each graph of diameter two and maximum degree dds, which is embeddable in S, has at most ⌊(3/2)d⌋ + 1 vertices. Moreover, this upper bound is best possible, and we show that extremal graphs can be found among surface triangulations. © 1997 John Wiley & Sons, Inc.  相似文献   

9.
In this note, we prove the following result. There is a positive constant ε(n, Λ) such that if M n is a simply connected compact Kähler manifold with sectional curvature bounded from above by Λ, diameter bounded from above by 1, and with holomorphic bisectional curvature H ≥ ?ε(n, Λ), then M n is diffeomorphic to the product M 1 × ? × M k , where each M i is either a complex projective space or an irreducible Kähler–Hermitian symmetric space of rank ≥ 2. This resolves a conjecture of Fang under the additional upper bound restrictions on sectional curvature and diameter.  相似文献   

10.
Let M n be a closed Riemannian manifold homotopy equivalent to the product of S 2 and an arbitrary (n–2)-dimensional manifold. In this paper we prove that given an arbitrary pair of points on M n there exist at least k distinct geodesics of length at most 20k!d between these points for every positive integer k. Here d denotes the diameter of M n .  相似文献   

11.
The connectivity index wα(G) of a graph G is the sum of the weights (d(u)d(v))α of all edges uv of G, where α is a real number (α≠0), and d(u) denotes the degree of the vertex u. Let T be a tree with n vertices and k pendant vertices. In this paper, we give sharp lower and upper bounds for w1(T). Also, for -1?α<0, we give a sharp lower bound and a upper bound for wα(T).  相似文献   

12.
In 1973, P. Erdös conjectured that for eachkε2, there exists a constantc k so that ifG is a graph onn vertices andG has no odd cycle with length less thanc k n 1/k , then the chromatic number ofG is at mostk+1. Constructions due to Lovász and Schriver show thatc k , if it exists, must be at least 1. In this paper we settle Erdös’ conjecture in the affirmative. We actually prove a stronger result which provides an upper bound on the chromatic number of a graph in which we have a bound on the chromatic number of subgraphs with small diameter.  相似文献   

13.
Given a connected graph Γ of order n and diameter d, we establish a tight upper bound for the order of the automorphism group of Γ as a function of n and d, and determine the graphs for which the bound is attained. © 2011 Wiley Periodicals, Inc. J Graph Theory.  相似文献   

14.
A generalized Latin square of type (n,k) is an n×n array of symbols 1,2,…,k such that each of these symbols occurs at most once in each row and each column. Let d(n,k) denote the cardinality of the minimal set S of given entries of an n×n array such that there exists a unique extension of S to a generalized Latin square of type (n,k). In this paper we discuss the properties of d(n,k) for k=2n-1 and k=2n-2. We give an alternate proof of the identity d(n,2n-1)=n2-n, which holds for even n, and we establish the new result . We also show that the latter bound is tight for n divisible by 10.  相似文献   

15.
16.
Let G be a k-connected simple graph with order n. The k-diameter, combining connectivity with diameter, of G is the minimum integer d k (G) for which between any two vertices in G there are at least k internally vertex-disjoint paths of length at most d k (G). For a fixed positive integer d, some conditions to insure d k (G)⩽d are given in this paper. In particular, if d⩾3 and the sum of degrees of any s (s=2 or 3) nonadjacent vertices is at least n+(s−1)k+1−d, then d k (G)⩽d. Furthermore, these conditions are sharp and the upper bound d of k-diameter is best possible. Supported by NNSF of China (19971086).  相似文献   

17.
We consider graphs of maximum degree 3, diameter D≥2 and at most 4 vertices less than the Moore bound M3,D, that is, (3,D,−?)-graphs for ?≤4.We prove the non-existence of (3,D,−4)-graphs for D≥5, completing in this way the catalogue of (3,D,−?)-graphs with D≥2 and ?≤4. Our results also give an improvement to the upper bound on the largest possible number N3,D of vertices in a graph of maximum degree 3 and diameter D, so that N3,DM3,D−6 for D≥5.  相似文献   

18.
It is known that if G is a connected simple graph, then G3 is Hamiltonian (in fact, Hamilton-connected). A simple graph is k-ordered Hamiltonian if for any sequence v1, v2,…,vk of k vertices there is a Hamiltonian cycle containing these vertices in the given order. In this paper, we prove that if k?4, then G⌊3k/2⌋-2 is k-ordered Hamiltonian for every connected graph G on at least k vertices. By considering the case of the path graph Pn, we show that this result is sharp. We also give a lower bound on the power of the cycle Cn that guarantees k-ordered Hamiltonicity.  相似文献   

19.
The spectra of some trees and bounds for the largest eigenvalue of any tree   总被引:2,自引:0,他引:2  
Let T be an unweighted tree of k levels such that in each level the vertices have equal degree. Let nkj+1 and dkj+1 be the number of vertices and the degree of them in the level j. We find the eigenvalues of the adjacency matrix and Laplacian matrix of T for the case of two vertices in level 1 (nk = 2), including results concerning to their multiplicity. They are the eigenvalues of leading principal submatrices of nonnegative symmetric tridiagonal matrices of order k × k. The codiagonal entries for these matrices are , 2 ? j ? k, while the diagonal entries are 0, …, 0, ±1, in the case of the adjacency matrix, and d1d2, …, dk−1dk ± 1, in the case of the Laplacian matrix. Finally, we use these results to find improved upper bounds for the largest eigenvalue of the adjacency matrix and of the Laplacian matrix of any given tree.  相似文献   

20.
We prove that for each k?0, the probability that a root vertex in a random planar graph has degree k tends to a computable constant dk, so that the expected number of vertices of degree k is asymptotically dkn, and moreover that kdk=1. The proof uses the tools developed by Giménez and Noy in their solution to the problem of the asymptotic enumeration of planar graphs, and is based on a detailed analysis of the generating functions involved in counting planar graphs. However, in order to keep track of the degree of the root, new technical difficulties arise. We obtain explicit, although quite involved expressions, for the coefficients in the singular expansions of the generating functions of interest, which allow us to use transfer theorems in order to get an explicit expression for the probability generating function p(w)=kdkwk. From this we can compute the dk to any degree of accuracy, and derive the asymptotic estimate dkck−1/2qk for large values of k, where q≈0.67 is a constant defined analytically.  相似文献   

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

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