Upper bounds on the length of a shortest closed geodesic and quantitative Hurewicz theorem

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 ⁿ , how “fast” can this sphere be contracted to a point, if π _i (M ⁿ )={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 ⁿ providing that M ⁿ is not k-connected?     

Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies

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 M_n,m matches the best known lower bound, and for all other pairs it differs from this lower bound by at most 2.     

An explicit formula for eigenvalues of Bethe trees and upper bounds on the largest eigenvalue of any tree

A Bethe tree B_d,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 B_d,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 B_d,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.     

An improvement of the Griesmer bound for some small minimum distances

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).     

Chain sequences and symmetric generalized orthogonal polynomials

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 K_n^(λ,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 K_n^(λ,M) which are the symmetric Koornwinder polynomials. Monotonicity properties of the zeros of K_n^(λ,M,k) in relation to M and k are also given.     

On the existence of graphs of diameter two and defect two

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=d²−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 AJ_n=dJ_n and A²+A+(1−d)I_n=J_n+B, where J_n 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 F_i,d(x)=f_i(x²+x+1−d), where f_i(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 F_i,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.     

On a generalization of distance sets

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.     

Extremal graphs of diameter two and given maximum degree,embeddable in a fixed surface

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 d_s such that each graph of diameter two and maximum degree d ≥ d_s, 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.     

Short Geodesic Segments between Two Points on a Closed Riemannian Manifold

Let M ⁿ be a closed Riemannian manifold homotopy equivalent to the product of S ² and an arbitrary (n–2)-dimensional manifold. In this paper we prove that given an arbitrary pair of points on M ⁿ 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 ⁿ .     

A note on K<Emphasis Type="Italic">ä</Emphasis>hler manifolds with almost nonnegative bisectional curvature

In this note, we prove the following result. There is a positive constant ε(n, Λ) such that if M ⁿ 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 ⁿ is diffeomorphic to the product M ₁ × ? × 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.     

Trees of extremal connectivity index

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 w₁(T). Also, for -1?α<0, we give a sharp lower bound and a upper bound for w_α(T).     

On coloring graphs with locally small chromatic number

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.     

Automorphism group and diameter of a graph

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.     

Generalized Latin squares and their defining sets

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)=n²-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.     

On k -diameter of k -connected graphs

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).     

Complete catalogue of graphs of maximum degree 3 and defect at most 4

We consider graphs of maximum degree 3, diameter D≥2 and at most 4 vertices less than the Moore bound M_3,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 N_3,D of vertices in a graph of maximum degree 3 and diameter D, so that N_3,D≤M_3,D−6 for D≥5.     

Graph powers and k-ordered Hamiltonicity

It is known that if G is a connected simple graph, then G³ is Hamiltonian (in fact, Hamilton-connected). A simple graph is k-ordered Hamiltonian if for any sequence v₁, v₂,…,v_k 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 P_n, we show that this result is sharp. We also give a lower bound on the power of the cycle C_n that guarantees k-ordered Hamiltonicity.     

The spectra of some trees and bounds for the largest eigenvalue of any tree

Let T be an unweighted tree of k levels such that in each level the vertices have equal degree. Let n_k−j+1 and d_k−j+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 (n_k = 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 d₁, d₂, …, d_k−1, d_k ± 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.     

Degree distribution in random planar graphs

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 k_∑dk=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)=k_∑dkwk. From this we can compute the dk to any degree of accuracy, and derive the asymptotic estimate dk∼c⋅k−1/2qk for large values of k, where q≈0.67 is a constant defined analytically.