In this paper we obtain some lower bounds for minus and signed domination numbers. We also prove and generalize a conjecture on the minus domination number for bipartite graph of order n, which was proposed by Jean Du...In this paper we obtain some lower bounds for minus and signed domination numbers. We also prove and generalize a conjecture on the minus domination number for bipartite graph of order n, which was proposed by Jean Dunbar et al [1].展开更多
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...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] = \sum\nolimits_{y \in N_T [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 .展开更多
Let G=(V,E)be a graph,for an element x∈V∪E,the open total neighborhood of x is denoted by N_(t)(x)={y|y is adjacent to x or y is incident with x,y∈V∪E},and Nt[x]=Nt(x)∪{x}is the closed one.A function f:V(G)∪E(G...Let G=(V,E)be a graph,for an element x∈V∪E,the open total neighborhood of x is denoted by N_(t)(x)={y|y is adjacent to x or y is incident with x,y∈V∪E},and Nt[x]=Nt(x)∪{x}is the closed one.A function f:V(G)∪E(G)→{−1,0,1}is said to be a mixed minus domination function(TMDF)of G if∑_(y∈Nt[x])f(y)≥1 holds for all x∈V(G)∪E(G).The mixed minus domination numberγ′_(tm)(G)of G is defined as γ′_(tm)(G)=min{∑x∈V∪E f(x)|f is a TMDF of G.In this paper,we obtain some lower bounds of the mixed minus domination number of G and give the exact values ofγ′_(tm)(G)when G is a cycle or a path.展开更多
For a graph G=(V,E),a Roman{2}-dominating function f:V→{0,1,2}has the property that for every vertex v∈V with f(v)=0,either v is adjacent to at least one vertex u for which f(u)=2,or at least two vertices u1 and u2 ...For a graph G=(V,E),a Roman{2}-dominating function f:V→{0,1,2}has the property that for every vertex v∈V with f(v)=0,either v is adjacent to at least one vertex u for which f(u)=2,or at least two vertices u1 and u2 for which f(u1)=f(u2)=1.A Roman{2}-dominating function f=(V0,V1,V2)is called independent if V1∪V2 is an independent set.The weight of an independent Roman{2}-dominating function f is the valueω(f)=Σv∈V f(v),and the independent Roman{2}-domination number i{R2}(G)is the minimum weight of an independent Roman{2}-dominating function on G.In this paper,we characterize all trees with i{R2}(T)=γ(T)+1,and give a linear time algorithm to compute the value of i{R2}(T)for any tree T.展开更多
基金Supported by the National Science Foundation of Jiangxi province(9911020).
文摘In this paper we obtain some lower bounds for minus and signed domination numbers. We also prove and generalize a conjecture on the minus domination number for bipartite graph of order n, which was proposed by Jean Dunbar et al [1].
基金the National Natural Science Foundation of China(Grant No.10471311)
文摘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] = \sum\nolimits_{y \in N_T [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 .
基金This work was supported by the National Natural Science Foundation of China(No.11061014,11361024,11261019)the Science Foundation of Jiangxi Province(No.KJLD12067)The authors are grateful to the referees for their careful reading with corrections and especially the referee who draws our attention to the proof in Theorem 2.2,which let us improve the proof of Theorem 2.2,and correct this lower bound.
文摘Let G=(V,E)be a graph,for an element x∈V∪E,the open total neighborhood of x is denoted by N_(t)(x)={y|y is adjacent to x or y is incident with x,y∈V∪E},and Nt[x]=Nt(x)∪{x}is the closed one.A function f:V(G)∪E(G)→{−1,0,1}is said to be a mixed minus domination function(TMDF)of G if∑_(y∈Nt[x])f(y)≥1 holds for all x∈V(G)∪E(G).The mixed minus domination numberγ′_(tm)(G)of G is defined as γ′_(tm)(G)=min{∑x∈V∪E f(x)|f is a TMDF of G.In this paper,we obtain some lower bounds of the mixed minus domination number of G and give the exact values ofγ′_(tm)(G)when G is a cycle or a path.
基金Supported by National Natural Science Foundation of China(Grant No.12171440)。
文摘For a graph G=(V,E),a Roman{2}-dominating function f:V→{0,1,2}has the property that for every vertex v∈V with f(v)=0,either v is adjacent to at least one vertex u for which f(u)=2,or at least two vertices u1 and u2 for which f(u1)=f(u2)=1.A Roman{2}-dominating function f=(V0,V1,V2)is called independent if V1∪V2 is an independent set.The weight of an independent Roman{2}-dominating function f is the valueω(f)=Σv∈V f(v),and the independent Roman{2}-domination number i{R2}(G)is the minimum weight of an independent Roman{2}-dominating function on G.In this paper,we characterize all trees with i{R2}(T)=γ(T)+1,and give a linear time algorithm to compute the value of i{R2}(T)for any tree T.
