首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到18条相似文献,搜索用时 46 毫秒
1.
设G=(V,E)是一个图,一个函数f:V→{-1,+1}如果满足Σv∈N[υ]f(ν)≥1对于每个点u∈V成立,则称f为图G的一个符号控制函数,图G的符号控制数γs(G)定义为γs(G)=min{Σv∈vf(v)|f为图G的符号控制函数},类似地,可定义图G的上符号控制数Γs(G).研究了几类特殊图的符号控制问题,获得了完全l等部图和乘积图P_3×P_n的符号控制数,并确定了P_2×P_n和P_3×P_n的上符号控制数.  相似文献   

2.
关于图的符号控制数的下界   总被引:7,自引:0,他引:7  
图的符号控制数的研究有许多应用背景,但图的符号控制数的计算是NP完全问题,因而确定其上下界有重大意义。本文在[5]的基础上,引进了新参数δ^*(G),全面改进了[5]所给出的符号控制数的下界,并给出了一些可达下界的图。  相似文献   

3.
设G=(V,E)是一个顶点集为V且边集为E的简单图.G的一个符号混合控制函数定义为函数f:V∪E→{-1,1},使得对每个元素x∈V∪E都有y∈Nm(x)∪{x}∑f(y)≥1成立.此处,Nm(x)是V∪E中与x相邻或关联的所有元素的集合.f的权为w(f)=∑ x∈V∪Ef(x).G的符号混合控制数γs*(G)定义为G...  相似文献   

4.
设G=(V,E)是一个图,u∈V,则E(u)表示u点所关联的边集.一个函数f:E→{-1,1}如果满足■f(e)≥1对任意v∈V成立,则称f为图G的一个符号星控制函数,图G的符号星控制数定义为γ'_(ss)(G)=min{■f(e):f为图G的一个符号星控制函数}.给出了几类特殊图的符号星控制数,主要包含完全图,正则偶图和完全二部图.  相似文献   

5.
通过对集合分组的方法,给出了图的结构性质.从而得到了符号控制数和强符号全控制数的6个下界,且这6个下界是最好可能的.  相似文献   

6.
关于图的弱符号控制数的下界   总被引:1,自引:0,他引:1  
图G的弱符号控制数γws(G)有着许多重要的应用背景,因而确定其下界有重要意义.在构造适当点集的基础上,给出了图的弱符号控制数的4个独立的下界,并给出了达到这4个下界的图.  相似文献   

7.
图的符号星k控制数   总被引:3,自引:0,他引:3  
引入了图的符号星k控制的概念.设G=(V,E)是一个图,一个函数f:E→{-1,+1},如果∑e∈E[v]f(e)≥1对于至少k个顶点v∈V(G)成立,则称f为图G的一个符号星k控制函数,其中E(v)表示G中与v点相关联的边集.图G的符号星k控制数定义为γkss(G)=min{∑e∈Ef(e)|f为图G的符号星k控制函数}.在本文中,我们主要给出了一般图的符号星k控制数的若干下界,推广了关于符号星控制的一个结果,并确定路和圈的符号星k控制数.  相似文献   

8.
9.
图G的符号控制数γs(G)有着许多重要的应用背景,因而确定其精确值有重要意义.Cm表示m个顶点的圈,n-Cm和n·Cm分别表示恰有一条公共边或一个公共顶点的n个Cm的拷贝.给出了n-Cm和n·Cm的符号控制数.  相似文献   

10.
关于图的符号边全控制数   总被引:1,自引:0,他引:1  
引入了图的符号边全控制的概念,给出了一个连通图G的符号边全控制数γs′t(G)的下限,确定所有n阶树T的最小符号边全控制数,并刻划了满足γs′t(G)=E(G)的所有连通图G,最后还提出了一个关于γs′t(G)上界的猜想.  相似文献   

11.
The open neighborhood N G (e) of an edge e in a graph G is the set consisting of all edges having a common end-vertex with e. Let f be a function on E(G), the edge set of G, into the set {−1, 1}. If for each eE(G), then f is called a signed edge total dominating function of G. The minimum of the values , taken over all signed edge total dominating function f of G, is called the signed edge total domination number of G and is denoted by γ st ′(G). Obviously, γ st ′(G) is defined only for graphs G which have no connected components isomorphic to K 2. In this paper we present some lower bounds for γ st ′(G). In particular, we prove that γ st ′(T) ⩾ 2 − m/3 for every tree T of size m ⩾ 2. We also classify all trees T with γ st ′(T). Research supported by a Faculty Research Grant, University of West Georgia.  相似文献   

12.
Let G =(V, E) be a simple graph with vertex set V and edge set E. A signed mixed dominating function of G is a function f:V∪E→ {-1, 1} such that ∑_(y∈N_m(x)∪{x})f(y)≥ 1for every element x∈V∪E, where N_m(x) is the set of elements of V∪E adjacent or incident to x. The weight of f is w(f) =∑_(x∈V∪E)f(x). The signed mixed domination problem is to find a minimum-weight signed mixed dominating function of a graph. In this paper we study the computational complexity of signed mixed domination problem. We prove that the signed mixed domination problem is NP-complete for bipartite graphs, chordal graphs, even for planar bipartite graphs.  相似文献   

13.
On signed majority total domination in graphs   总被引:1,自引:0,他引:1  
We initiate the study of signed majority total domination in graphs. Let G = (V, E) be a simple graph. For any real valued function f: V and S V, let . A signed majority total dominating function is a function f: V {–1, 1} such that f(N(v)) 1 for at least a half of the vertices v V. The signed majority total domination number of a graph G is = min{f(V): f is a signed majority total dominating function on G}. We research some properties of the signed majority total domination number of a graph G and obtain a few lower bounds of .This research was supported by National Natural Science Foundation of China.  相似文献   

14.
近年来,研究图的符号星控制数颇引人注目,研究了完全二部图的符号星控制数.  相似文献   

15.
设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符号边控制数.  相似文献   

16.
本文研究了图的符号团边控制数的问题.利用鸽巢原理,获得了图KnPmKnCm的符号团边控制数,推广了已有的结果.  相似文献   

17.
The paper studies the signed domination number and the minus domination number of the complete bipartite graph K p, q .  相似文献   

18.
A lower bound on the total signed domination numbers of graphs   总被引:4,自引:0,他引:4  
Let G be a finite connected simple graph with a vertex set V(G)and an edge set E(G). A total signed domination function of G is a function f:V(G)∪E(G)→{-1,1}.The weight of f is W(f)=∑_(x∈V)(G)∪E(G))f(X).For an element x∈V(G)∪E(G),we define f[x]=∑_(y∈NT[x])f(y).A total signed domination function of G is a function f:V(G)∪E(G)→{-1,1} such that f[x]≥1 for all x∈V(G)∪E(G).The total signed domination numberγ_s~*(G)of G is the minimum weight of a total signed domination function on G. In this paper,we obtain some lower bounds for the total signed domination number of a graph G and compute the exact values ofγ_s~*(G)when G is C_n and P_n.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号