排序方式: 共有9条查询结果,搜索用时 15 毫秒
1
1.
一个社会网络中通常包括具有正面影响和负面影响的两类人员,为了研究这个社会网络中人们之间相互影响的某些规律,引入了一个新的概念. 用划分图G=(V,E),V=V+ \cup V-表示这样的一个社会网络,其中V+和V- 分别表示正面人员的集合和负面人员的集合. 图G的一个点子集D\subseteq V-被称为G的一个正影响集,若G的每个点的至少一半的邻点在D\cup V+中. G的所有正影响集的最小基数称为G的正影响数. 给出G的正影响数的几个下界并证明了这些界是紧的. 此外,还证明了求正影响数问题在二部图和弦图上都是NP-完全的. 相似文献
2.
3.
4.
The 2-step domination problem is to find a minimum vertex set D of a graph such that every vertex of the graph is either in D or at distance two from some vertex of D.In the present paper,by using a labeling method,we provide an O(m) time algorithm to solve the2-step domination problem on block graphs,a superclass of trees. 相似文献
5.
A set D of vertices in a graph G = (V, E) is a locating-dominating set (LDS) if for every two vertices u, v of V / D the sets N(u) ∩D and N(v) ∩ D are non-empty and different. The locating-domination number γL(G) is the minimum cardinality of an LDS of G, and the upper-locating domination number FL(G) is the maximum cardinality of a minimal LDS of G. In the present paper, methods for determining the exact values of the upper locating-domination numbers of cycles are provided. 相似文献
6.
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. 相似文献
7.
8.
9.
$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$为偶数并且各部的顶点数相同的情况下,我们得到了这一参数的若干下界和上界. 相似文献
1