共查询到18条相似文献,搜索用时 62 毫秒
1.
变更图的直径 总被引:4,自引:0,他引:4
对于给定的正整数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. 相似文献
2.
3.
关于3连通图的容错直径和宽直径 总被引:5,自引:0,他引:5
容错直径和宽直径是度量网络可靠性和有效性的重要参数.对任意k连通图,它的容错直径Dk不超过宽直径dk,本证明:当D2=2时,d3≤max{D, l,2D3-2};当D2≥3时,d3≤(D2-1)[2(D2-1)(D3-1)-D2-2] 1. 相似文献
5.
对于任意的正数M以及正整数d≥4,存在直径为d的i-边连通无环图G使得ζ(G)≥M,其中ζ(G)是G的Betti亏数,i=1,2,3。 相似文献
6.
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. 相似文献
7.
一个给定的图是否存在用r种颜色的正常Pk着色?称该问题为图的(k,r)路色数问题。已知对于直径为2的图及任意给定的整数r≥3,图的(2,r)路色数问题是NP-完全的。本文给出直径为2的(2,2)路色图的一个好的刻划,并由此给出该问题的一个多项式时间算法,从而解决了以r为参数的直径为2的图的(2,r)路色数问题的计算复杂性分类。 相似文献
8.
变换图的直径及Brualdi猜想 总被引:1,自引:0,他引:1
设R=(r1,r2…rm)及 S=(S1,S2,…,Sn)为两个正整数向量,满足Σmi=1ri=Σnj=1sj= K.记G(R,S)为(0,1)-矩阵类 U(R,S)的变换图.Brualdi在文山中给出了 G(R,S)的直径厂(G(R,S))的一个上界:mn/2-1,并猜想D(G(R,S))≤mn/4.本文通过对有向图围长的研究得到了D(G(R,S))的一个新的上界:1/2mn-1/6t(t-1)(4t+1),其中T= . 相似文献
9.
10.
温一慧 《数学的实践与认识》2008,38(15)
通常没有有效的方法判别一般图G的k-边幻性.本文采用分析方法,讨论了一类非均匀边裂图SPE(Cn,h)的边幻性和k-边幻性,得到一些新的结果. 相似文献
11.
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. 相似文献
12.
13.
14.
An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles.The acyclic edge chromatic number of a graph G is the minimum number k such that there exists an acyclic edge coloring using k colors and is denoted by χ’ a(G).In this paper we prove that χ ’ a(G) ≤(G) + 5 for planar graphs G without adjacent triangles. 相似文献
15.
16.
Sanming Zhou 《Journal of Graph Theory》2014,75(1):37-47
Unitary graphs are arc‐transitive graphs with vertices the flags of Hermitian unitals and edges defined by certain elements of the underlying finite fields. They played a significant role in a recent classification of a class of arc‐transitive graphs that admit an automorphism group acting imprimitively on the vertices. In this article, we prove that all unitary graphs are connected of diameter two and girth three. Based on this, we obtain, for any prime power , a lower bound of order on the maximum number of vertices in an arc‐transitive graph of degree and diameter two. 相似文献
17.
18.
若干图的广义Mycielski图的边色数 总被引:1,自引:1,他引:1
设图G(V,E)为简单图,V(Mn(G))={v01,v02,…,v0p;v11,v12,…,v1p;…,vn1,vn2,…,vnp}EMn(G))=E(G)∪vijv(i+1)kv0 jv0k∈E(G),1 j,k p,i=0,1,…,n-1称Mn(G)为G的n串广义M ycielsk i图,其中n为自然数,V(G)={v01,v02,…,v0p}.本文得到了路、圈、扇、轮、星图的广义M ycielsk i图的边色数. 相似文献