变种超方体网络的容错直径与宽直径

研究变种超方体的网络容错直径和宽直径,证明了n维变种超立方体的n-1容错直径和n宽直径为[2n/3]+1或[2n/3]+2.     

Star图互连网络的容错性分析

限制连通度和限制容错直径是衡量互连网络可靠性的两个重要参数。当考察这两个参数时，总假设网络中和一台计算机相连接的所有计算机不会同时出现故障。该文证明了Star图互连网络的极小分离集和极小限制分离集的唯一性，然后得到了Star图的限制连通度是2n-4，当n=3,5和n≥7时，它的限制容错直径是|_3(n-1)/2_|+2，对于n =4, 6，限制容错直径是|_3(n-1)/2_|+3，即限制容错直径只比它的容错直径大1。     

变更图的直径

对于给定的正整数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.     

广义Fibonacci立方体的网络容错性质分析

主要研究广义Fibonacci立方体的容错直径和宽直径,证明了n维Fibonacci立方体网络的k-1容错直径和k宽直径都是n-1,其中k=[n/3].     

连通无向图Rabin数的一个界

可靠性和有效性是互连网络设计的重要标准,而Rabin数是度量网络容错性和传输延迟的重要参数.将通过图的容错直径给出2- 连通无向图和~3- 连通无向图的~Rabin 数r_2(G)和r_3(G)的界;同时也得到r_2(G) = D_2(G)成立的一个条件.     

与直径和围长有关的图的最大亏格

利用图的直径和围长来研究图的最大亏格的下界,得到了如下结果：设G是直径为d的简单图,若G的围长不小于d（其中d为不小于3的整数）,则ξ（G）≤2,即γM（G）≥1/2β（G）-1．而且,在这种意义下,所得到的界是最好的．     

变更图的直径

P(t,n)和C(t,n)分别表示在阶为n的路和圈中添加t条边后得到的图的最小直径；f(t,k)表示从直径为k的图中删去t条边后得到的连通图的最大直径．这篇文章证明了t≥4且n≥5时,P(t,n)≤(n-8)/(t 1) 3；若t为奇数,则C(t,n)≤(n-8)/(t 1) 3；若t为偶数,则C(t,n)≤(n-7)/(t 2) 3．特别地,「(n-1)/5」≤P(4,n)≤「(n 3)/5」,「n/4」-1≤C(3,n)≤「n/4」．最后,证明了：若k≥3且为奇数,则f(t,k)≥(t 1)k-2t 4．这些改进了某些已知结果．     

广义Petersen图的宽直径

广义Petersen图是一类重要的并被广泛研究的互连网络。本文证明了广义Petersen图 P(m,2)的直径和3宽直径分别为O(m/4)和O(m/3)。     

直径为三的不可上嵌入的图

本文证明了只存在一类3-边连通的直径为三的12个点的不可上嵌入的图.     

一类直径为2的极大平面图的Mostar指数

图G的Mostar指数定义为Mo(G)=∑uv∈Ε(G)|nu-nv|,其中nu表示在G中到顶点u的距离比到顶点v的距离近的顶点个数,nv表示到顶点v的距离比到顶点u的距离近的顶点个数.若一个图G的任两点之间的距离至多为2,且不是完全图,则称G是一个直径为2的图.已知直径为2点数至少为4的极大平面图的最小度为3或4.本文研究了直径为2且最小度为4的极大平面图的Mostar指数.具体说,若G是一个点数为n,直径为2,最小度为4的极大平面图,则(1)当n≤12时,Mostar指数被完全确定;(2)当n≥13时,4/3n2-44/3n+94/3≤Mo(G)≤2n2-16n+24,且达到上,下界的极图同时被找到.     

广义Petersen图的宽直径

Generalized Petersen graphs are commonly used interconnection networks,and wide diameter is an important parameter to measure fault-tolerance and efficiency of parallel pro- cessing computer networks.In this paper,we show that the diameter and 3-wide diameter of generalized Petersen graph P (m,a) are both O( m 2a ),where a ≥ 3.     

Counting Hyperbolic Manifolds with Bounded Diameter

Let ρ _n (V) be the number of complete hyperbolic manifolds of dimension n with volume less than V . Burger et al [Geom. Funct. Anal. 12(6) (2002), 1161–1173.] showed that when n ≥ 4 there exist a, b > 0 depending on the dimension such that aV log V ≤ log ρ _n (V) ≤ bV log V, for V ≫ 0. In this note, we use their methods to bound the number of hyperbolic manifolds with diameter less than d and show that the number grows double-exponentially with volume. Additionally, this bound holds in dimension 3.     

A Hypercube Variant with Small Diameter

This article introduces a new variant of hypercubes . The n‐dimensional twisted hypercube is obtained from two copies of the ‐dimensional twisted hypercube by adding a perfect matching between the vertices of these two copies of . We prove that the n‐dimensional twisted hypercube has diameter . This improves on the previous known variants of hypercube of dimension n and is optimal up to an error of order . Another type of hypercube variant that has similar structure and properties as is also discussed in the last section.     

On the Diameter of Plane Curves

Recently, differential geometric properties of embedded projective varieties have gained increasing interest. In this note, we consider plane algebraic curves equipped with the Fubini--Study metric from₂ () and give an estimate for the diameter in terms of the degree, initiated in a paper by F. A. Bogomolov.     

Restricted Fault Diameter of Hypercube Networks

This paper studies restricted fault diameter of the n-dimensional hypercube networks Qn (n ≥ 2).It is shown that for arbitrary two vertices x and y with the distance d in Qn and any set F with at most 2n-3 vertices in Qn - {x, y}, if F contains neither of neighbor-sets of x and y in Qn, then the distance between x andy in Qn - F is given by D(Qn-F;x,y){=1 , for=1;≤d 4 , for 2≤d≤n-2,n≥4;≤n 1, for d=n-1,n≥3; =n, for d=n. Furthermore, the upper bounds are tight. As an immediately consequence, Qn can tolerate up to 2n-3 vertices failures and remain diameter 4 if n = 3 and n 2 if n ≥ 4 provided that for each vertex x in Qn, all the neighbors of x do not fail at the same time. This improves Esfahanian‘s result.     

Pebbling Graphs of Diameter Three and Four

Given a configuration of pebbles on the vertices of a connected graph G, a pebbling move is defined as the removal of two pebbles from some vertex and the placement of one of these on an adjacent vertex. The pebbling number of a graph G is the smallest integer k such that for each vertex v and each configuration of k pebbles on G there is a sequence of pebbling moves that places at least one pebble on v. We improve on a bound of Bukh by showing that the pebbling number of a graph of diameter three on n vertices is at most , and this bound is best possible. Further, we obtain an asymptotic bound of for the pebbling number of graphs of diameter four. Finally, we prove an asymptotic bound for pebbling graphs of arbitrary diameter, namely that the pebbling number for a diameter d graph on n vertices is at most , where is a constant depending upon d. This also improves another bound of Bukh.     

给定直径的单圈图的超Wiener指数

The hyper-Wiener index is a kind of extension of the Wiener index, used for predicting physicochemical properties of organic compounds. The hyper-Wiener index W W(G) is defined as WW(G) =1/2∑_(u,v)∈V(G)(d_G(u, v) + d_G~2(u,v)) with the summation going over all pairs of vertices in G, d_G(u,v) denotes the distance of the two vertices u and v in the graph G. In this paper,we study the minimum hyper-Wiener indices among all the unicyclic graph with n vertices and diameter d, and characterize the corresponding extremal graphs.     

Total Domination in Graphs with Diameter 2

The total domination number of a graph G is the minimum cardinality of a set S of vertices, so that every vertex of G is adjacent to a vertex in S. In this article, we determine an optimal upper bound on the total domination number of a graph with diameter 2. We show that for every graph G on n vertices with diameter 2, . This bound is optimal in the sense that given any , there exist graphs G with diameter 2 of all sufficiently large even orders n such that .