变更图的直径

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连通图的容错直径和宽直径

容错直径和宽直径是度量网络可靠性和有效性的重要参数．对任意k连通图，它的容错直径Dk不超过宽直径dk,本证明：当D2=2时，d3≤max{D， l，2D3-2}；当D2≥3时，d3≤(D2-1)[2(D2-1)(D3-1)-D2-2] 1．     

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

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

图的直径与Betti亏数

对于任意的正数Ｍ以及正整数ｄ≥４,存在直径为ｄ的ｉ－边连通无环图Ｇ使得ζ（Ｇ）≥Ｍ,其中ζ（Ｇ）是Ｇ的Ｂｅｔｔｉ亏数,ｉ＝１,２,３。     

将小直径图划分为导出匹配

Given a simple graph G and a positive integer k, the induced matching k-partition problem asks whether there exists a k-partition (V1,V2,…Vk)of V(G) such that for each i(1≤i≤k),G[Vi] is 1 regular. This paper studies the computational complexity of this problem for graphs with small diameters. The main results are as follows: Induced matching 2-partition problem of graphs with diameter 6 and induced matching 3-partition problem of graphs with diameter 2 are NP- complete;induced matching 2-partition problem of graphs with diameter 2 is polynomially solvable.     

直径为2的图的P2路色问题

一个给定的图是否存在用ｒ种颜色的正常Ｐｋ着色？称该问题为图的（ｋ，ｒ）路色数问题。已知对于直径为２的图及任意给定的整数ｒ≥３，图的（２，ｒ）路色数问题是ＮＰ－完全的。本文给出直径为２的（２，２）路色图的一个好的刻划，并由此给出该问题的一个多项式时间算法，从而解决了以ｒ为参数的直径为２的图的（２，ｒ）路色数问题的计算复杂性分类。     

变换图的直径及Brualdi猜想

设Ｒ＝（ｒ１，ｒ２…ｒｍ）及 Ｓ＝（Ｓ１，Ｓ２，…，Ｓｎ）为两个正整数向量，满足Σｍｉ＝１ｒｉ＝Σｎｊ＝１ｓｊ＝ Ｋ．记Ｇ（Ｒ，Ｓ）为（０，１）－矩阵类 Ｕ（Ｒ，Ｓ）的变换图．Ｂｒｕａｌｄｉ在文山中给出了 Ｇ（Ｒ，Ｓ）的直径厂（Ｇ（Ｒ，Ｓ））的一个上界：ｍｎ／２－１，并猜想Ｄ（Ｇ（Ｒ，Ｓ））≤ｍｎ／４．本文通过对有向图围长的研究得到了Ｄ（Ｇ（Ｒ，Ｓ））的一个新的上界：１／２ｍｎ－１／６ｔ（ｔ－１）（４ｔ＋１），其中Ｔ＝　　．     

关于环网的直径

1.引言 环网G(N;s_1,s_2,…,s_r)是正则的有向循环图。其节点集用V={0,1,2,…,N-1}表示。N是自然数。网中,从每个节点i向节点i+s_j(modN)都有一条有向弧(i,i+s_j)(i=0,1,…,N-1;j=1,2,…,r;0相似文献   

关于一类边裂图的k-边幻性

通常没有有效的方法判别一般图G的k-边幻性.本文采用分析方法,讨论了一类非均匀边裂图SPE(Cn,h)的边幻性和k-边幻性,得到一些新的结果.     

On the Diameter of Wenger Graphs

Let q be a prime power, the field of q elements, and n≥1 a positive integer. The Wenger graph W _n (q) is defined as follows: the vertex set of W _n (q) is the union of two copies P and L of (n+1)-dimensional vector spaces over , with two vertices (p ₁,p ₂,…,p _n+1)∈P and [l ₁,l ₂,…,l _n+1]∈L being adjacent if and only if l _i +p _i =p ₁ l _i−1 for 2≤i≤n+1. Graphs W _n (q) have several interesting properties. In particular, it is known that when connected, their diameter is at most 2n+2. In this note we prove that the diameter of connected Wenger graphs is 2n+2 under the assumption that 1≤n≤q−1.     

Diameters of uniform subset graphs

Let r,s be positive integers with r>s, k a nonnegative integer, and n=2r−s+k. A uniform subset graph G(n,r,s) is a graph with vertex set [n]^r and where two r-subsets A,B∈[n]^r are adjacent if and only if |A∩B|=s. Let denote the diameter of a graph G.In this paper, we prove the following results: (1) If k>0, then if r≥2s+k+2, 2 if k≥s and 2s≤r≤s+k, or k<s and s+k≤r≤2s, and 3 otherwise; (2) If k=0, then . This generalizes a result in [M. Valencia-Pabon, J.-C. Vera, On the diameter of Kneser graphs, Discrete Math. 305 (2005) 383-385].     

Super Restricted Edge Connectivity of Regular Graphs

An edge cut of a connected graph is called restricted if it separates this graph into components each having order at least 2; a graph G is super restricted edge connected if G−S contains an isolated edge for every minimum restricted edge cut S of G. It is proved in this paper that k-regular connected graph G is super restricted edge connected if k > |V(G)|/2+1. The lower bound on k is exemplified to be sharp to some extent. With this observation, we determined the number of edge cuts of size at most 2k−2 of these graphs. Supported by NNSF of China (10271105); Ministry of Science and Technology of Fujian (2003J036); Education Ministry of Fujian (JA03147)     

有向P2-路图的结构性质

一个有向图D的有向Pk-路图Pk(D)是通过把D中的所有有向k长路作为点集;两点u= x1x2…xk+1,v=y1y2…yk+1之间有弧uv当xi=yi-1,i=2,3,…,k+1.明显地,当k=1时Pk(D)就是通常的有向线图L(D).在[1,2]中,P2-路图得到完整刻画.在[3]中,Broersma等人研究了有向...     

On the Reverse Wiener Indices of Unicyclic Graphs

We determine the maximum values of the reverse Wiener indices of the unicyclic graphs with given cycle length, number of pendent vertices and maximum degree, respectively, and characterize the extremal graphs. We also determine the unicyclic graphs of given cycle length and diameter with minimum Wiener index.      

Sizes of Critical Graphs with Small Maximum Degrees

In this paper, we give new lower bounds for the size of Δ-critical graphs with Δ=8,9 which improve the partial results of Luo [6] and Y. Zhao [12].     

一类偶阶图的边优美性

本文讨论了一类偶阶图的边优美性。同时得到了完全图是边优美图的充要条件。     

链状正则图的平均距离

本文构造了一类链状正则图G_k∶δ,求出了它们的平均距离D(G_k.δ),并得到关系式上式等号成立当且仅当δ=4f且k=0.这个估计式指出了施容华猜想[1]D(G)≤n/(δ 1)不成立. 文中进一步证明了这一类链状正则图有最大的直径,所以可以作出猜想: 若G是n阶连通图,则D(G)<(n 1)/(δ 1),其中δ是图G的最小度。