共查询到20条相似文献,搜索用时 15 毫秒
1.
Huajun Tang 《Discrete Mathematics》2008,308(15):3416-3419
Let G=(V,E) be a graph. A signed dominating function on G is a function f:V→{-1,1} such that for each v∈V, where N[v] is the closed neighborhood of v. The weight of a signed dominating function f is . A signed dominating function f is minimal if there exists no signed dominating function g such that g≠f and g(v)?f(v) for each v∈V. The upper signed domination number of a graph G, denoted by Γs(G), equals the maximum weight of a minimal signed dominating function of G. In this paper, we establish an tight upper bound for Γs(G) in terms of minimum degree and maximum degree. Our result is a generalization of those for regular graphs and nearly regular graphs obtained in [O. Favaron, Signed domination in regular graphs, Discrete Math. 158 (1996) 287-293] and [C.X. Wang, J.Z. Mao, Some more remarks on domination in cubic graphs, Discrete Math. 237 (2001) 193-197], respectively. 相似文献
2.
H. Karami S. M. Sheikholeslami Abdollah Khodkar 《Czechoslovak Mathematical Journal》2008,58(3):595-603
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 e ∈ E(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. 相似文献
3.
A lower bound on the total signed domination numbers of graphs 总被引:4,自引:0,他引:4
Xin-zhong LU Department of Mathematics Zhejiang Normal University Jinhua China 《中国科学A辑(英文版)》2007,50(8):1157-1162
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. 相似文献
4.
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. 相似文献
5.
关于图的强符号全控制数 总被引:1,自引:0,他引:1
图的强符号全控制数有着许多重要的应用背景,因而确定其下界有重要的意义.本文提出了图的强符号全控制数的概念,在构造适当点集的基础上对其进行了研究,给出了:(1)一般图的强符号全控制数的5个独立可达的下界及达到其界值的图;(2)确定了圈、轮图、完全图、完全二部图的强符号全控制数的值. 相似文献
6.
关于图的弱符号控制数的下界 总被引:1,自引:0,他引:1
图G的弱符号控制数γws(G)有着许多重要的应用背景,因而确定其下界有重要意义.在构造适当点集的基础上,给出了图的弱符号控制数的4个独立的下界,并给出了达到这4个下界的图. 相似文献
7.
特殊图类的符号控制数 总被引:2,自引:1,他引:2
王军秀 《纯粹数学与应用数学》2005,21(1):59-61
图G的符号控制数γS(G)有着许多重要的应用背景.已知它的计算是NP-完全问题,因而确定其上下界有重要意义.本文研究了1)一般图G的符号控制数,给出了一个新的下界;2)确定了Cn图的符号控制数的精确值. 相似文献
8.
9.
10.
11.
Gašper Mekiš 《Discrete Mathematics》2010,310(23):3310-3317
A sharp lower bound for the domination number and the total domination number of the direct product of finitely many complete graphs is given: . Sharpness is established in the case when the factors are large enough in comparison to the number of factors. The main result gives a lower bound for the domination (and the total domination) number of the direct product of two arbitrary graphs: γ(G×H)≥γ(G)+γ(H)−1. Infinite families of graphs that attain the bound are presented. For these graphs it also holds that γt(G×H)=γ(G)+γ(H)−1. Some additional parallels with the total domination number are made. 相似文献
12.
Three numerical invariants of graphs concerning domination, which are named the signed domination number γs, the k-subdomination number γks and the signed total domination number γst, are studied in this paper. For any graph, some lower bounds on γs, γks and γst are presented, some of which generalize several known lower bounds on γs, γks and γst, while others are considered as new. It is also shown that these bounds are sharp. 相似文献
13.
Let β(G), Γ(G) and IR(G) be the independence number, the upper domination number and the upper irredundance number, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every induced subgraph H of G. A graph G is called IR-perfect if Γ(H) =IR(H), for every induced subgraph H of G. In this paper, we present a characterization of Γ-perfect graphs in terms of a family of forbidden induced subgraphs, and show that the class of Γ-perfect graphs is a subclass of IR-perfect graphs and that the class of absorbantly perfect graphs is a subclass of Γ-perfect graphs. These results imply a number of known theorems on Γ-perfect graphs and IR-perfect graphs. Moreover, we prove a sufficient condition for a graph to be Γ-perfect and IR-perfect which improves a known analogous result. 相似文献
14.
Let G=(V(G),E(G)) be a graph. A function f:E(G)→{+1,−1} is called the signed edge domination function (SEDF) of G if ∑e′N[e]f(e′)≥1 for every eE(G). The signed edge domination number of G is defined as is a SEDF of G}. Xu [Baogen Xu, Two classes of edge domination in graphs, Discrete Applied Mathematics 154 (2006) 1541–1546] researched on the edge domination in graphs and proved that for any graph G of order n(n≥4). In the article, he conjectured that: For any 2-connected graph G of order n(n≥2), . In this note, we present some counterexamples to the above conjecture and prove that there exists a family of k-connected graphs Gm,k with . 相似文献
15.
A numerical invariant of directed graphs concerning domination which is named signed domination number γS is studied in this paper. We present some sharp lower bounds for γS in terms of the order, the maximum degree and the chromatic number of a directed graph. 相似文献
16.
17.
18.
19.
对树的3-彩虹控制数进行研究,首先用构造法找到直径较小的树的3-彩虹控制数的上界.再通过分类讨论思想和数学归纳法得到一般的阶n大于等于5的树的3-彩虹控制数的上界. 相似文献
20.
Two classes of edge domination in graphs 总被引:2,自引:0,他引:2
Baogen Xu 《Discrete Applied Mathematics》2006,154(10):1541-1546
Let (, resp.) be the number of (local) signed edge domination of a graph G [B. Xu, On signed edge domination numbers of graphs, Discrete Math. 239 (2001) 179-189]. In this paper, we prove mainly that and hold for any graph G of order n(n?4), and pose several open problems and conjectures. 相似文献