共查询到18条相似文献,搜索用时 140 毫秒
1.
特殊图类的符号控制数 总被引:2,自引:1,他引:1
王军秀 《纯粹数学与应用数学》2005,21(1):59-61
图G的符号控制数γS(G)有着许多重要的应用背景.已知它的计算是NP-完全问题,因而确定其上下界有重要意义.本文研究了1)一般图G的符号控制数,给出了一个新的下界;2)确定了Cn图的符号控制数的精确值. 相似文献
2.
3.
图的弱罗马控制数是图的弱罗马控制函数(简称WRDF)的最小权,记为γr(G).本文确定了完全n部图的弱罗马控制数,根据罗马控制数的下界以及弱罗马控制数与罗马控制数、控制数之间的关系,确定了弱罗马控制数的下界,运用概率方法给出了弱罗马控制数的上界. 相似文献
4.
图的弱罗马控制数是图的弱罗马控制函数(简称WRDF)的最小权,记为γr(G).本文确定了完全n部图的弱罗马控制数,根据罗马控制数的下界以及弱罗马控制数与罗马控制数、控制数之间的关系,确定了弱罗马控制数的下界,运用概率方法给出了弱罗马控制数的上界. 相似文献
5.
6.
图的强符号全控制数有着许多重要的应用背景,因而确定其下界有重要的意义.本文提出了图的强符号全控制数的概念,在构造适当点集的基础上对其进行了研究,给出了:(1)一般图的强符号全控制数的5个独立可达的下界及达到其界值的图;(2)确定了圈、轮图、完全图、完全二部图的强符号全控制数的值. 相似文献
7.
8.
引入了图的符号星部分控制的概念.设G=(V,E)是一个简单连通图, M是V的一个子集.一个函数f:E→{-1,1}若满足∑e∈E(v)f(e)≥1对M中的每个顶点v都成立,则称f是图G的一个符号星部分控制函数,其中E(v)表示G中与v点相关连的边集.图G的符号星部分控制数定义为γM(85)(G)=min{∑e∈Ef(e)|f是G的符号星部分控制函数}.在本文中我们主要给出了一般图的符号星部分控制数的上界和下界,并确定了路、圈和完全图的符号星部分控制数的精确值.作为我们引入的这一新概念的一个应用,求出了完全图的符号星k控制数. 相似文献
9.
10.
11.
Bohdan Zelinka 《Czechoslovak Mathematical Journal》2002,52(4):875-879
The signed edge domination number and the signed total edge domination number of a graph are considered; they are variants of the domination number and the total domination number. Some upper bounds for them are found in the case of the n-dimensional cube Q
n. 相似文献
12.
13.
关于图的减控制与符号控制 总被引:18,自引:2,他引:18
给定一个图G=(V,E),一个函数f:V→{-1,0,1}被称为G的减控制函数,如果对任意v∈V(G)均有∑μ∈N[v]f(μ)≥1。G的减控制数定义为γ-(G)=min{∑v∈Vf(v)|f是G的减控制函数}。图G的符号控制函数的正如减控制函数,差别是广{-1,0,1}换成{-1,1}。符号控制数γs(G)是类似的。本文获得γ-G)和γs(G)的一些下界。同时也证明并推广了 Jean Dunbar等提出的一个猜想,即对任意 n阶 2部图 G,均有γ-(G)≥ 4(n+11/2-1)-n成立。 相似文献
14.
关于图的团符号控制数 总被引:2,自引:0,他引:2
引入了图的团符号控制的概念,给出了n阶图G的团符号控制数γks(G)的若干下限,确定了几类特殊图的团符号控制数,并提出了若干未解决的问题和猜想. 相似文献
15.
16.
17.
设G=(V,E)是一个图,一个函数f:E→{-1,+1},如果对于G中至少k条边e有sum from e'∈N[e]f(e')≥1成立,则称f为图G的一个k符号边控制函数.一个图的k符号边控制数定义为γ_(ks)/(G)=min{∑_(e∈E(G))f(e)|f为图G的一个k符号边控制函数}.主要给出了一个图G的k符号边控制数γ_(ks)/(G)=min{∑_(e∈E(G))f(e)|f为图G的一个k符号边控制函数}.主要给出了一个图G的k符号边控制数γ_(ks)/(G)的若干新下限,并确定了路和圈的k符号边控制数. 相似文献
18.