一类联图的符号边控制数

设G=(V,E)是一个简单图,一个函数f:E→{-1,1},若满足∑_(e′∈N[e])f(e)≥1对E(G)中的每个边e都成立,则称f是图G的一个符号边控制函数,图G的符号边控制数定义为γ′_s(G)=min{∑_(e∈E)f(e)|f是G的符号边控制函数}.给出了联图C_(2k)+C_(2k)的符号边控制数.     

图的逆符号边控制数的上界

设G=(V,E)是一个图,对于图G的-个函数f:E→{-1,1},如果对任意e∈E(G),均有∑f(e')≤1,则称,为图G的一个逆符号边控制函数.图G的逆符号边控制数(～γ's)(G)=e'∈N[e]max{∑,(e)|f,为图G的一个逆符号边控制函数}.本文在定义了逆符号边控制数的基础上,得到了图e∈E的逆符号边控制数的几个上界.     

两类特殊图的逆符号边控制数

设G=(V,E)是一个图,对于图G的一个函数f:E→{-1,1},如果对任意e∈E(G),均有Σe′∈N[e]f(e′)≤1,则称f为图G的一个逆符号边控制函数.图G的逆符号边控制数γ′s(G)=max{Σe∈E(G)f(e)|f为图G的一个逆符号边控制函数}.在逆符号边控制数定义基础上,得到了所有轮图和扇图的逆符号边控制数.     

两类特殊图的逆符号边控制数

设G=(V,E)是一个图,对于图G的一个函数f:E→{-1,1},如果对任意e∈E(G),均有Σe′∈N[e]f(e′)≤1,则称f为图G的一个逆符号边控制函数.图G的逆符号边控制数γ′s(G)=max{Σe∈E(G)f(e)|f为图G的一个逆符号边控制函数}.在逆符号边控制数定义基础上,得到了所有轮图和扇图的逆符号边控制数.     

图的符号星k控制数

引入了图的符号星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控制数.     

图的符号星部分控制数

引入了图的符号星部分控制的概念.设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控制数.     

关于给定符号圈控制数的图的刻画（英文）

设G=(V,E)是简单图.称一个函数f:E→{+1,-1}为图G的符号圈控制函数,若对G的每一导出圈C,有Σ_(e∈)E(C)f(e)≥1.G的符号圈控制数被定义为γ′_(sc)(G)=min{∑_(e∈E)f(e)|f是G的符号圈控制函数}.本文刻画了所有具有γ′_(sc)(G)=|E|-4的连通图G.     

关于图的符号星控制数

设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的一个符号星控制函数}.给出了几类特殊图的符号星控制数,主要包含完全图,正则偶图和完全二部图.     

几类图的Fractional星控制数

设G=(V,E)是一个无孤立点的图,一个实值函数f:E(G)→[0,1]若对所有的点u∈V(G),均有∑uv∈Ef(uv)≥1成立,则称f为图G的一个Fractional星控制函数.图G的Fractional星控制数定义为γ_(fs)(G)=min{∑uv∈Ef(uv)|f为图G的一个Fractional星控制函数}.研究了几类乘积图的Fractional星控制问题,给出了一些常见特殊图的Fractional星控制数,主要确定了积图P_m×P_n和C_m×P_n的Fractional星控制数.     

几类图的符号控制

设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的上符号控制数.     

完全多部图的符号边控制数的界

$f: E(G)\rightarrow\{-1,1\}$称为图$G =(V,E)$的一个符号边控制函数 (简称SEDF),如果$f[e]=f(N[e])=\sum_{e''\in N[e]}f(e'')\geq1$对于图$G$的每条边$e\in E$都成立. $w(f)=\sum_{e\in E}f(e)$称为函数$f$的权. $G$的符号边控制数$\gamma_{s}\,''(G)$是指$G$的所有符号边控制函数的最小权.本文对完全多部图的符号边控制数进行研究.对于完全$r$-部图, 当$r$为偶数并且各部的顶点数相同的情况下,我们得到了这一参数的若干下界和上界.     

关于图的符号边全控制数

Let G = （V,E） be a graph.A function f ： E → {-1,1} is said to be a signed edge total dominating function （SETDF） of G if e ∈N（e） f（e ） ≥ 1 holds for every edge e ∈ E（G）.The signed edge total domination number γ st （G） of G is defined as γ st （G） = min{ e∈E（G） f（e）｜f is an SETDF of G}.In this paper we obtain some new lower bounds of γ st （G）.     

完全图全符号控制数的较小上界和下确界

设图G=G(V,E),令函数f∶V∪E→{-1,1},f的权w(f)=∑x∈V∪Ef[x],对V∪E中任一元素,定义f[x]=∑y∈NT[x]f(y),这里NT[x]表示V∪E中x及其关联边、邻点的集合.图G的全符号控制函数为f∶V∪E→{-1,1},满足对所有的x∈V∪E有f[x]1,图G的全符号控制数γT(G)就是图G上全符号控制数的最小权,称其f为图G的γT-函数.本文得到了完全图全符号控制数的一个较小上界和下确界.     

Signed Roman (Total) Domination Numbers of Complete Bipartite Graphs and Wheels

A signed(res. signed total) Roman dominating function, SRDF(res.STRDF) for short, of a graph G =(V, E) is a function f : V → {-1, 1, 2} satisfying the conditions that(i)∑v∈N[v]f(v) ≥ 1(res.∑v∈N(v)f(v) ≥ 1) for any v ∈ V, where N [v] is the closed neighborhood and N(v) is the neighborhood of v, and(ii) every vertex v for which f(v) =-1 is adjacent to a vertex u for which f(u) = 2. The weight of a SRDF(res. STRDF) is the sum of its function values over all vertices.The signed(res. signed total) Roman domination number of G is the minimum weight among all signed(res. signed total) Roman dominating functions of G. In this paper,we compute the exact values of the signed(res. signed total) Roman domination numbers of complete bipartite graphs and wheels.     

符号混合控制问题的某些NP-完全性结果

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.     

关于图的符号边全控制数

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

On signed majority total domination in graphs

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.     

P_n~2和P_n~(n-1)的均匀邻强边色数

对阶至少为3的简单连通图G的k-正常边染色法f,若对任意uv∈E(G)有C(u)≠C(v),Ei-Ej 1,i,j=1,2,…,k.其中C(u)={f(uv)uv∈E(G)},Ei={uv f(uv)=i,uv∈E(G)},则称f为G的一k-均匀邻强边染色,简称k-EASEC.并称χe′as(G)=min{k k-EASEC of G}为G的均匀邻强边色数.给出了图Pn2与Pnn-1的均匀邻强边色数.