排序方式: 共有86条查询结果,搜索用时 772 毫秒
11.
A set D of vertices of a graph G = (V, E) is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a dominating set of cardinality at most 3n/8. In this paper we generalize Reed's result. We show that every graph G of order n with minimum degree at least 2 has a dominating set of cardinality at most (3n +IV21)/8, where V2 denotes the set of vertices of degree 2 in G. As an application of the above result, we show that for k ≥ 1, the k-restricted domination number rk (G, γ) ≤ (3n+5k)/8 for all graphs of order n with minimum degree at least 3. 相似文献
12.
3-γ-临界图G中关于i(G)=γ(G)的一个充分条件 总被引:1,自引:0,他引:1
如果图G满足γ(G)=k且对图G中任两个相邻的点x,y有γ(G+xy)=k-1,则称图G为k-γ-临界图,如果图G满足γ(G)=k且对图G中任何距离为d的两点x,y有γ(G+xy)=k-1,则称图G为k-(γ,d)-临界图。Sumner和Blitch猜想在3-γ-临界图中有γ(G)=i(G).Oellermann和Swart猜想3-(γ,2)-临界图中有γ(G)=i(G),这篇文章中我们提出3-γ-临界图中使γ(G)=i(G)的一个充分条件。 相似文献
13.
14.
直径为d的超环面网的(d,2n)-控制数 总被引:2,自引:0,他引:2
n维超环面网C(dl,d2,…,dn)定义如下顶点集为{(x1,..,xn)|0≤xi<di(1≤i≤n)};每个顶点(xl,…,xn)与(x1±1,x2,…,xn),(xl,x2±1,…,xn),…,(x1,x2,….,xn±1)这2n个顶点相邻.(d,m)-控制数是用来刻画互连网络数据传输某种模式的一个新参数.本文证明了当d=diam(C(d1,d2,…,dn))时,n维超环面网C(d1,d2,…,dn)≠C(3,3,….,3)的(d,2n)控制数为2(n≥3,di≥3,i∈{1,2,…,n}. 相似文献
15.
16.
17.
广义de Bruijn和Kautz有向图的距离控制数 总被引:1,自引:0,他引:1
对于任意的正整数(?),强连通图G的顶点子集D被称为距离(?)-控制集,是指对于任意顶点v(?)D,D中至少含有一个顶点u,使得距离dG(u,v)≤(?).图G距离(?)- 控制数γe(G)是指G中所有距离(?)-控制集的基数的最小者.本文给出了广义de Bruijn 和广义Kautz有向图的距离(?)-控制数的上界和下界,并且给出当它们的距离2-控制数达到下界时的一个充分条件.从而得到对于de Bruijn有向图B(d,k)的距离2-控制数γ2(B(d,k))= .在该文结尾,我们猜想Kautz有向图K(d,k)的距离2-控制数γ2(K(d,k))= . 相似文献
18.
关于图的团符号控制数 总被引:2,自引:0,他引:2
引入了图的团符号控制的概念,给出了n阶图G的团符号控制数γks(G)的若干下限,确定了几类特殊图的团符号控制数,并提出了若干未解决的问题和猜想. 相似文献
19.
对树的3-彩虹控制数进行研究,首先用构造法找到直径较小的树的3-彩虹控制数的上界.再通过分类讨论思想和数学归纳法得到一般的阶n大于等于5的树的3-彩虹控制数的上界. 相似文献
20.