Distance and size in digraphs

We determine the maximum number of arcs in an Eulerian digraph of given order and diameter. Our bound generalises a classical result on the maximum number of edges of an undirected graph of given order and diameter by Ore (1968) and Homenko and Ostroverhii? (1970). We further determine the maximum size of a bipartite digraph of given order and radius.     

A NOTE ON COMPLETE MANIFOLDS WITH FINITE VOLUME

In this article, we concern on complete manifolds with finite volume. We prove that under some assumptions about scalar curvature and the Yamabe constant, the manifolds must be compact, and we also give the diameter estimates in terms of the scalar curvature and the Yamabe constant.     

变更图的直径

对于给定的正整数t和d(≥2),用F(t,d)和P(t,d)分别表示在所有直径为d的图和路中添加t条边后得到的图的最小直径,用f(t, d)表示从所有直径为d的图中删去t条边后得到的图的最大直径. 已经证明P(1, d)=(d)/(2), P(2,d)=(d 1)/(3)和P(3, d)=(d 2)/(4). 一般地,当t和d≥4时有(d 1)/(t 1)-1≤P(t, d)≤(d 1)/(t 1) 3. 在这篇文章中,我们得到F(t, f(t, d))≤d≤f(t, F(t, d))和(d)/(t 1)≤F(t, d)=P(t, d)≤(d-2)/(t 1) 3,而且当d充分大时,F(t, d)≤(d)/(t) 1. 特别地,对任意正整数k有P(t, (2k-1)(t 1) 1)=2k,当t=4或5,且d≥4时有(d)/(t 1)≤P(t, d)≤(d)/(t 1) 1.     

Optimal fault-tolerant routings with small routing tables for k-connected graphs

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 n2k², in which the route degree is , the total number of routes is O(k²n) 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 ρ₁ for every n-node biconnected graph, in which the total number of routes is O(n) and D(R(G,ρ₁)/{f})2 for any fault f, and a routing ρ₂ (using ρ₁) for every n-node biconnected graph, in which the route degree is , the total number of routes is and D(R(G,ρ₂)/{f})2 for any fault f.     

ON THE TOPOLOGY,VOLUME,DIAMETER AND GAUSS MAP IMAGE OF SUBMANIFOLDS IN A SPHERE

In this paper, the author uses Gauss map to study the topology, volume and diameter of submanifolds in a sphere. It is proved that if there exist ε, 1≥ε > 0 and a fixed unit simple p-vector a such that the Gauss map g of an n-dimensional complete and connected submanifold M in Sn p satisfies (g, a) ≥ε, then M is diffeomorphic to Sn, and the volume and diameter of M satisfy εnvol(Sn) ≤vol(M) ≤ vol(Sn)/ε and επ ≤diam(M) ≤ π/ε, respectively. The author also characterizes the case where these inequalities become equalities. As an application, a differential sphere theorem for compact submanifolds in a sphere is obtained.     

The number of independent sets in unicyclic graphs with a given diameter

Let U_n,d denote the set of unicyclic graphs with a given diameter d. In this paper, the unique unicyclic graph in U_n,d with the maximum number of independent sets, is characterized.     

Permutation polytopes and indecomposable elements in permutation groups

Each group G of n×n permutation matrices has a corresponding permutation polytope, P(G):=conv(G)⊂Rn×n. We relate the structure of P(G) to the transitivity of G. In particular, we show that if G has t nontrivial orbits, then min{2t,⌊n/2⌋} is a sharp upper bound on the diameter of the graph of P(G). We also show that P(G) achieves its maximal dimension of ²(n−1) precisely when G is 2-transitive. We then extend the results of Pak [I. Pak, Four questions on Birkhoff polytope, Ann. Comb. 4 (1) (2000) 83-90] on mixing times for a random walk on P(G). Our work depends on a new result for permutation groups involving writing permutations as products of indecomposable permutations.     

Maximally edge-connected and vertex-connected graphs and digraphs: A survey

Let D be a graph or a digraph. If δ(D) is the minimum degree, λ(D) the edge-connectivity and κ(D) the vertex-connectivity, then κ(D)?λ(D)?δ(D) is a well-known basic relationship between these parameters. The graph or digraph D is called maximally edge-connected if λ(D)=δ(D) and maximally vertex-connected if κ(D)=δ(D). In this survey we mainly present sufficient conditions for graphs and digraphs to be maximally edge-connected as well as maximally vertex-connected. We also discuss the concept of conditional or restricted edge-connectivity and vertex-connectivity, respectively.     

JCJ-ⅡT二维激光测径仪

介绍了一种可用于玻璃管、导线、棒材等生产线上外径的在线非接触检测与控制的二维激光测径仪,叙述了二维激光扫描测径的原理及二维激光测径仪的结构及实现.