共查询到20条相似文献,搜索用时 85 毫秒
1.
研究变种超方体的网络容错直径和宽直径,证明了n维变种超立方体的n-1容错直径和n宽直径为[2n/3]+1或[2n/3]+2. 相似文献
2.
3.
4.
本文证明了若G是连通、局部连通的无爪图,则G是泛连通图的充要条件为G是3-连通图.这意味着H.J.Broersma和H.J.Veldman猜想成立. 相似文献
5.
本文所讨论的图均为无向、有限简单图。文中没有指明的记号、术语见[3]。图G的欧拉生成子图是一条经过G的所有顶点的闭迹,以下简称S-闭迹。 相似文献
7.
8.
h连通图中非临界点的个数 总被引:1,自引:0,他引:1
设G是h连通的简单非完全图,v中G的顶点,若k(G-v)≥k(G),则称v是G的非临界点,关于G中非临界点的个数,Veldman和苏健基分别给定了在不同条件下的下界,本文推广了他们的结果,得到了更一般的下界。 相似文献
9.
10.
图的广义连通度的概念是由Chartrand等人引入的.令S表示图G的一个非空顶点集,κ(S)表示图G中连结S的内部不交树的最大数目.那么,对任意一个满足2≤r≤n的整数r,定义G的广义r-连通度为所有κ(S)中的最小值,其中S取遍G的顶点集合的r-元子集.显然,κ_2(G)=κ(G),即为图G的顶点连通度.所以广义连通度是经典连通度的一个自然推广.本文研究了随机图的广义3-连通度,证明了对任一给定的整数k,k≥1,p=(log n+(k+1)log long n-log lon logn)/n是关于性质κ_3(G(n,p))≥k的紧阈值函数.我们得到的结果可以看作是Bollobas和Thomason给出的关于经典连通度结果的推广. 相似文献
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.
Raymond Viglione 《Acta Appl Math》2008,104(2):173-176
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
1,p
2,…,p
n+1)∈P and [l
1,l
2,…,l
n+1]∈L being adjacent if and only if l
i
+p
i
=p
1
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. 相似文献
13.
Hao Li 《Graphs and Combinatorics》2000,16(3):319-335
Let G be a 3-connected graph of order n and S a subset of vertices. Denote by δ(S) the minimum degree (in G) of vertices of S. Then we prove that the circumference of G is at least min{|S|, 2δ(S)} if the degree sum of any four independent vertices of S is at least n+6. A cycle C is called S-maximum if there is no cycle C
′ with |C
′∩S|>|C∩S|. We also show that if ∑4
i=1
d(a
i)≥n+3+|⋂4
i=1
N(a
i)| for any four independent vertices a
1, a
2, a
3, a
4 in S, then G has an S-weak-dominating S-maximum cycle C, i.e. an S-maximum cycle such that every component in G−C contains at most one vertex in S.
Received: March 9, 1998 Revised: January 7, 1999 相似文献
14.
Lai, Shao and Zhan (J Graph Theory 48:142–146, 2005) showed that every 3-connected N 2-locally connected claw-free graph is Hamiltonian. In this paper, we generalize this result and show that every 3-connected claw-free graph G such that every locally disconnected vertex lies on some induced cycle of length at least 4 with at most 4 edges contained in some triangle of G is Hamiltonian. It is best possible in some sense. 相似文献
15.
An arc of a graph is an oriented edge and a 3-arc is a 4-tuple (v,u,x,y) of vertices such that both (v,u,x) and (u,x,y) are paths of length two. The 3-arc graph of a given graph G, X(G), is defined to have vertices the arcs of G. Two arcs uv,xy are adjacent in X(G) if and only if (v,u,x,y) is a 3-arc of G. This notion was introduced in recent studies of arc-transitive graphs. In this paper we study diameter and connectivity of 3-arc graphs. In particular, we obtain sharp bounds for the diameter and connectivity of X(G) in terms of the corresponding invariant of G. 相似文献
16.
17.
An edge e in a simple 3-connected graph is deletable (simple-contractible) if the deletion G\e (contraction G/e) is both simple and 3-connected. Suppose a, b, and c are three non-negative integers. If there exists a simple 3-connected graph with exactly a edges which are deletable but not simple-contractible, exactly b edges which are simple-contractible but not deletable, and exactly c edges which are both deletable and simple-contractible, then we call the triple (a, b, c) realizable, and such a graph is said to be an (a, b, c)-graph. Tutte's Wheels Theorem says the only (0, 0, 0)-graphs are the wheels. In this paper, we characterize the (a, b, c) realizable triples for which at least one of a + b≤2, c=0, and c≥16 holds.
Received: February 12, 1997 Revised: February 13, 1998 相似文献
18.
该文证明了如下结果:设犌为直径为4的简单图,若犌不含3阶完全子图犓3,则犌的Betti亏数ξ(犌)≤4,因此有犌的最大亏格γ犕(犌)≥
12β(犌)-2. 相似文献
19.
Elkin Vumar 《Graphs and Combinatorics》2006,22(2):271-282
A graph G is quasi-claw-free if it satisfies the property: d(x,y)=2 ⇒ there exists such that . In the paper, we prove that the circumference of a 3-connected quasi-claw-free graph G on n vertices is at least min{4δ−2,n} and G is hamiltonian if n≤5δ−5. 相似文献
20.
Matthias Kriesell 《Graphs and Combinatorics》2006,22(4):481-485
Let κ(G) denote the (vertex) connectivity of a graph G. For ℓ≥0, a noncomplete graph of finite connectivity is called ℓ-critical if κ(G−X)=κ(G)−|X| for every X⊆V(G) with |X|≤ℓ.
Mader proved that every 3-critical graph has diameter at most 4 and asked for 3-critical graphs having diameter exceeding
2. Here we give an affirmative answer by constructing an ℓ-critical graph of diameter 3 for every ℓ≥3. 相似文献