We investigate the dominating-c-color number,, of a graph G. That is the maximum number of color classes that are also dominating when G is colored using colors. We show that where is the join of G and . This result a...We investigate the dominating-c-color number,, of a graph G. That is the maximum number of color classes that are also dominating when G is colored using colors. We show that where is the join of G and . This result allows us to construct classes of graphs such that and thus provide some information regarding two questions raised in [1] and [2].展开更多
A Roman dominating function on a graph G = （V, E） is a function f ： V→{0, 1, 2} satisfying the condition that every vertex u for which f（u） = 0 is adjacent to at least one vertex v for which f（v） = 2. The weig...A Roman dominating function on a graph G = （V, E） is a function f ： V→{0, 1, 2} satisfying the condition that every vertex u for which f（u） = 0 is adjacent to at least one vertex v for which f（v） = 2. The weight of a Roman dominating function is the value f（V） = Σu∈Vf（u）. The minimum weight of a Roman dominating function on a graph G, denoted by γR（G）, is called the Roman dominating number of G. In this paper, we will characterize a tree T with γR（T） = γ（T） ＋ 3.展开更多
In this paper, the diversity information included by dominating number is analyzed, and the probabilistic relationship between dominating number and diversity in the space of objective function is proved. A ranking me...In this paper, the diversity information included by dominating number is analyzed, and the probabilistic relationship between dominating number and diversity in the space of objective function is proved. A ranking method based on dominating number is proposed to build the Pareto front. Without increasing basic Pareto method’s computation complexity and introducing new parameters, a new multiobjective genetic algorithm based on proposed ranking method (MOGA-DN) is presented. Simulation results on function optimization and parameters optimization of control system verify the efficiency of MOGA-DN.展开更多
Let G=(V, E) be a simple graph without an isolate. A subset T of V is a total dominating set of G if for any there exists at least one vertex such that .The total domination number γ1(G) of G is the minimum order of...Let G=(V, E) be a simple graph without an isolate. A subset T of V is a total dominating set of G if for any there exists at least one vertex such that .The total domination number γ1(G) of G is the minimum order of a total dominating set of G. This paper proves that if G is a connected graph with n≥3 vertices and minimum degree at least two.展开更多
Let G=(V,E) be a simple graph. For any real valued function f∶V→R and SV, let f(S)=∑ u∈S?f(u). A majority dominating function is a function f∶V→{-1,1} such that f(N)≥1 for at least half the vertices v∈V. Th...Let G=(V,E) be a simple graph. For any real valued function f∶V→R and SV, let f(S)=∑ u∈S?f(u). A majority dominating function is a function f∶V→{-1,1} such that f(N)≥1 for at least half the vertices v∈V. Then majority domination number of a graph G is γ maj(G)=min{f(V)|f is a majority dominating function on G}. We obtain lower bounds on this parameter and generalize some results of Henning.展开更多
Let G = （V, E） be a graph, and let f ： V →{-1, 1} be a two-valued function. If ∑x∈N（v） f（x） ≥ 1 for each v ∈ V, where N（v） is the open neighborhood of v, then f is a signed total dominating function on ...Let G = （V, E） be a graph, and let f ： V →{-1, 1} be a two-valued function. If ∑x∈N（v） f（x） ≥ 1 for each v ∈ V, where N（v） is the open neighborhood of v, then f is a signed total dominating function on G. A set {fl, f2,… fd} of signed d total dominating functions on G with the property that ∑i=1^d fi（x） ≤ 1 for each x ∈ V, is called a signed total dominating family （of functions） on G. The maximum number of functions in a signed total dominating family on G is the signed total domatic number on G, denoted by dt^s（G）. The properties of the signed total domatic number dt^s（G） are studied in this paper. In particular, we give the sharp bounds of the signed total domatic number of regular graphs, complete bipartite graphs and complete graphs.展开更多
Let γ＊（D） denote the twin domination number of digraph D and let Cm Cn denote the Cartesian product of C_m and C_n, the directed cycles of length m, n ≥ 2. In this paper, we determine the exact values： γ＊（C_2...Let γ＊（D） denote the twin domination number of digraph D and let Cm Cn denote the Cartesian product of C_m and C_n, the directed cycles of length m, n ≥ 2. In this paper, we determine the exact values： γ＊（C_2□C_n） = n; γ＊（C_3 □C_n） = n if n ≡ 0（mod 3）,otherwise, γ＊（C_3□C_n） = n ＋ 1; γ＊（C_4□C_n） = n ＋ n/2 if n ≡ 0, 3, 5（mod 8）, otherwise,γ＊（C_4□C_n） = n ＋ n/2 ＋ 1; γ＊（C_5□C_n） = 2n; γ＊（C_6□C_n） = 2n if n ≡ 0（mod 3）, otherwise,γ＊（C_6□C_n） = 2n ＋ 2.展开更多
A subset S of V is called a k-connected dominating set if S is a dominating set and the induced subgraph S has at most k components.The k-connected domination number γck（G） of G is the minimum cardinality taken ove...A subset S of V is called a k-connected dominating set if S is a dominating set and the induced subgraph S has at most k components.The k-connected domination number γck（G） of G is the minimum cardinality taken over all minimal k-connected dominating sets of G.In this paper,we characterize trees and unicyclic graphs with equal connected domination and 2-connected domination numbers.展开更多
Wireless sensor networks(WSNs)are one of the most important improvements due to their remarkable capacities and their continuous growth in various applications.However,the lifetime of WSNs is very confined because of ...Wireless sensor networks(WSNs)are one of the most important improvements due to their remarkable capacities and their continuous growth in various applications.However,the lifetime of WSNs is very confined because of the delimited energy limit of their sensor nodes.This is the reason why energy conservation is considered the main exploration worry for WSNs.For this energy-efficient routing is required to save energy and to subsequently drag out the lifetime of WSNs.In this report we use the Ant Colony Optimization(ACO)method and are evaluated using the Genetic Algorithm(GA),based on the Detour non-split dominant set(GA)In this research,we use the energy efficiency returnee non-split dominating set(DNSDS).A set S⊆V is supposed to be a DNSDS of G when the graph G=(V,E)is expressed as both detours as well as a non-split dominating set of G.Let the detour non-split domination number be addressed asγ_dns(G)and is the minimum order of its detour non-split dominating set.Any DNSDS of orderγdns(G)is aγdns-set of G.Here,theγ_dns(G)of various standard graphs is resolved and some of its general properties are contemplated.A connected graph usually has an order n with detour non-split domination number as n or n–1 are characterized.Also connected graphs of order n≥4 and detour diameter D≤4 with detour non-split dominating number n or n−1 or n−2 are additionally portrayed.While considering any pair of positive integers to be specific a and b,there exists a connected graph G which is normally indicated as dn(G)=a,γ(G)=b andγdns(G)=a+b−2,hereγdns(G)indicates the detour domination number and dn(G)indicates the detour number of a graph.The time is taken for the construction and the size of DNSDS are considered for examining the performance of the proposed method.The simulation result confirms that the DNSDS nodes are energy efficient.展开更多
The bondage number of γ f, b f(G) , is defined to be the minimum cardinality of a set of edges whose removal from G results in a graph G′ satisfying γ f(G′)> γ f(G) . The reinforcement number of γ f, ...The bondage number of γ f, b f(G) , is defined to be the minimum cardinality of a set of edges whose removal from G results in a graph G′ satisfying γ f(G′)> γ f(G) . The reinforcement number of γ f, r f(G) , is defined to be the minimum cardinality of a set of edges which when added to G results in a graph G′ satisfying γ f(G′)< γ f(G) . G.S.Domke and R.C.Laskar initiated the study of them and gave exact values of b f(G) and r f(G) for some classes of graphs. Exact values of b f(G) and r f(G) for complete multipartite graphs are given and some results are extended.展开更多
Let γ^＊（D） denote the twin domination number of digraph D and let Di× D 2 denote the strong product of Di and D 2. In this paper, we obtain that the twin domination number of strong product of tw...Let γ^＊（D） denote the twin domination number of digraph D and let Di× D 2 denote the strong product of Di and D 2. In this paper, we obtain that the twin domination number of strong product of two directed cycles of length at least 2. Furthermore, we give a lower bound of the twin domination number of strong product of two digraphs, and prove that the twin domination number of strong product of the complete digraph and any digraph D equals the twin domination number of D.展开更多
A function f:E(G)→{−1,1}is called a signed edge dominating function(SEDF for short)of G if f[e]=f(N[e])=Σ_( e′∈N[e])f(e′)≥1,for every edge e∈E(G).w(f)=Σ_(e∈E) f(e)is called the weight of f.The signed edge dom...A function f:E(G)→{−1,1}is called a signed edge dominating function(SEDF for short)of G if f[e]=f(N[e])=Σ_( e′∈N[e])f(e′)≥1,for every edge e∈E(G).w(f)=Σ_(e∈E) f(e)is called the weight of f.The signed edge domination numberγs′(G)of G is the minimum weight among all signed edge dominating functions of G.In this paper,we initiate the study of this parameter for G a complete multipartite graph.We provide the lower and upper bounds ofγs′(G)for G a complete r-partite graph with r even and all parts equal.展开更多
Let <img src="Edit_092a0db1-eefa-4bff-81a0-751d038158ad.png" width="58" height="20" alt="" /> be a graph. A function <img src="Edit_b7158ed5-6825-41cd-b7f0-5ab5e16...Let <img src="Edit_092a0db1-eefa-4bff-81a0-751d038158ad.png" width="58" height="20" alt="" /> be a graph. A function <img src="Edit_b7158ed5-6825-41cd-b7f0-5ab5e16fc53d.png" width="79" height="20" alt="" /> is said to be a Signed Dominating Function (SDF) if <img src="Edit_c6e63805-bcaa-46a9-bc77-42750af8efd4.png" width="135" height="25" alt="" /> holds for all <img src="Edit_bba1b366-af70-46cd-aefe-fc68869da670.png" width="42" height="20" alt="" />. The signed domination number <img src="Edit_22e6d87a-e3be-4037-b4b6-c1de6a40abb0.png" width="284" height="25" alt="" />. In this paper, we determine the exact value of the Signed Domination Number of graphs <img src="Edit_36ef2747-da44-4f9b-a10a-340c61a3f28c.png" width="19" height="20" alt="" /> and <img src="Edit_26eb0f74-fcc2-49ad-8567-492cf3115b73.png" width="19" height="20" alt="" /> for <img src="Edit_856dbcc1-d215-4144-b50c-ac8a225d664f.png" width="32" height="20" alt="" />, which is generalized the known results, respectively, where <img src="Edit_4b7e4f8f-5d38-4fd0-ac4e-dd8ef243029f.png" width="19" height="20" alt="" /> and <img src="Edit_6557afba-e697-4397-994e-a9bda83e3219.png" width="19" height="20" alt="" /> are denotes the k-th power graphs of cycle <img src="Edit_27e6e80f-85d5-4208-b367-a757a0e55d0b.png" width="21" height="20" alt="" /> and path <img src="Edit_70ac5266-950b-4bfd-8d04-21711d3ffc33.png" width="18" height="20" alt="" />.展开更多
The relations among the dominating number, independence number and covering number of hypergraphs are investigated. Main results are as follows：Dv（H）≤min{α≤（H）, p（H）, p（H）, T（H）}; De（H）≤min{v（H）, T...The relations among the dominating number, independence number and covering number of hypergraphs are investigated. Main results are as follows：Dv（H）≤min{α≤（H）, p（H）, p（H）, T（H）}; De（H）≤min{v（H）, T（H）, p（H）}; DT（H） ≤αT（H）; S（H）≤ Dv （H） ＋ α（H）≤n; 2≤ Dv （H） ＋ T（H） ≤n; 2 〈 Dv （H） ＋ v（H）≤n/2 ＋ [n/r]; Dv （H） ＋ p（H） 〈_n;2≤De（H） ＋ Dv（H）≤n/2 ＋ [n/r];α（H） ＋ De（H）≤n;2 ≤ De（H） ＋ v（H）≤2[n/r]; 2 De（H） ＋ p（H）≤n-r ＋ 2.展开更多
The study of minus paired domination of a graph G=(V,E) is initiated. Let SV be any paired dominating set of G , a minus paired dominating function is a function of the form f∶V→{-1,0,1} such that ...The study of minus paired domination of a graph G=(V,E) is initiated. Let SV be any paired dominating set of G , a minus paired dominating function is a function of the form f∶V→{-1,0,1} such that f(v)= 1 for v∈S, f(v)≤0 for v∈V-S , and f(N)≥1 for all v∈V . The weight of a minus paired dominating function f is w(f)=∑f(v) , over all vertices v∈V . The minus paired domination number of a graph G is γ - p( G )=min{ w(f)|f is a minus paired dominating function of G }. On the basis of the minus paired domination number of a graph G defined, some of its properties are discussed.展开更多
Let G=(V,E) be a simple graph. For any real valued function f:V →R, the weight of f is f(V) = ∑f(v) over all vertices v∈V . A signed total dominating function is a function f:V→{-1,1} such ...Let G=(V,E) be a simple graph. For any real valued function f:V →R, the weight of f is f(V) = ∑f(v) over all vertices v∈V . A signed total dominating function is a function f:V→{-1,1} such that f(N(v)) ≥1 for every vertex v∈V . The signed total domination number of a graph G equals the minimum weight of a signed total dominating function on G . In this paper, some properties of the signed total domination number of a graph G are discussed.展开更多
Let G = （V,E） be a simple graph. For any real function g ： V →R and a subset S 包涵于V, we write g（S） = ∑v∈sg（v）. A function f ： V → [0,1] is said to be a fractional dominating function （FDF） of G if f（...Let G = （V,E） be a simple graph. For any real function g ： V →R and a subset S 包涵于V, we write g（S） = ∑v∈sg（v）. A function f ： V → [0,1] is said to be a fractional dominating function （FDF） of G if f（N[v]） ≥ 1 holds for every vertex v ∈ V（G）. The fractional domination number γf（G） of G is defined as γf（G） = min{f（V）｜f is an FDF of G }. The fractional total dominating function f is defined just as the fractional dominating function, the difference being that f（N（v）） ≥ 1 instead of f（N[v]）≥ 1. The fractional total domination number γ^0f（G） of G is analogous. In this note we give the exact values of γf（Cm× Pn） and γ^0f（Cm × Pn） for all integers m ≥ 3 and n ≥ 2.展开更多
Let γ f(G) and γ~t f(G) be the fractional domination number and fractional total domination number of a graph G respectively. Hare and Stewart gave some exact fractional domination number of P n...Let γ f(G) and γ~t f(G) be the fractional domination number and fractional total domination number of a graph G respectively. Hare and Stewart gave some exact fractional domination number of P n×P m (grid graph) with small n and m . But for large n and m , it is difficult to decide the exact fractional domination number. Motivated by this, nearly sharp upper and lower bounds are given to the fractional domination number of grid graphs. Furthermore, upper and lower bounds on the fractional total domination number of strong direct product of graphs are given.展开更多
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： VUE→{-1,1}such that ∑y∈Nm（x）U{x}f（y） ≥1 for every element x ∈ V U E, where Nm （x...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： VUE→{-1,1}such that ∑y∈Nm（x）U{x}f（y） ≥1 for every element x ∈ V U E, where Nm （x） is the set of elements of V U E adjacent or incident to x. The weight of f isw（f）∑x∈VUEf（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.展开更多
文摘We investigate the dominating-c-color number,, of a graph G. That is the maximum number of color classes that are also dominating when G is colored using colors. We show that where is the join of G and . This result allows us to construct classes of graphs such that and thus provide some information regarding two questions raised in [1] and [2].
基金Supported by the NSF of education Department of Henan Province(200510475038)
文摘A Roman dominating function on a graph G = （V, E） is a function f ： V→{0, 1, 2} satisfying the condition that every vertex u for which f（u） = 0 is adjacent to at least one vertex v for which f（v） = 2. The weight of a Roman dominating function is the value f（V） = Σu∈Vf（u）. The minimum weight of a Roman dominating function on a graph G, denoted by γR（G）, is called the Roman dominating number of G. In this paper, we will characterize a tree T with γR（T） = γ（T） ＋ 3.
基金supported by the Academic Outstanding Youth Talented Person Fund of Anhui Province (No.2009SQR2014)
文摘In this paper, the diversity information included by dominating number is analyzed, and the probabilistic relationship between dominating number and diversity in the space of objective function is proved. A ranking method based on dominating number is proposed to build the Pareto front. Without increasing basic Pareto method’s computation complexity and introducing new parameters, a new multiobjective genetic algorithm based on proposed ranking method (MOGA-DN) is presented. Simulation results on function optimization and parameters optimization of control system verify the efficiency of MOGA-DN.
文摘Let G=(V, E) be a simple graph without an isolate. A subset T of V is a total dominating set of G if for any there exists at least one vertex such that .The total domination number γ1(G) of G is the minimum order of a total dominating set of G. This paper proves that if G is a connected graph with n≥3 vertices and minimum degree at least two.
文摘Let G=(V,E) be a simple graph. For any real valued function f∶V→R and SV, let f(S)=∑ u∈S?f(u). A majority dominating function is a function f∶V→{-1,1} such that f(N)≥1 for at least half the vertices v∈V. Then majority domination number of a graph G is γ maj(G)=min{f(V)|f is a majority dominating function on G}. We obtain lower bounds on this parameter and generalize some results of Henning.
基金Project supported by the National Natural Science Foundation of China （Grant No.1057117）, and the Science Foundation of Shanghai Municipal Commission of Education （Grant No.05AZ04）.
文摘Let G = （V, E） be a graph, and let f ： V →{-1, 1} be a two-valued function. If ∑x∈N（v） f（x） ≥ 1 for each v ∈ V, where N（v） is the open neighborhood of v, then f is a signed total dominating function on G. A set {fl, f2,… fd} of signed d total dominating functions on G with the property that ∑i=1^d fi（x） ≤ 1 for each x ∈ V, is called a signed total dominating family （of functions） on G. The maximum number of functions in a signed total dominating family on G is the signed total domatic number on G, denoted by dt^s（G）. The properties of the signed total domatic number dt^s（G） are studied in this paper. In particular, we give the sharp bounds of the signed total domatic number of regular graphs, complete bipartite graphs and complete graphs.
基金Supported by the National Natural Science Foundation of China(Grant Nos.6136302011301450+2 种基金11226294)the Youth Science and Technology Education Project of Xinjiang(Grant No.2013731011)China Scholarship Council
文摘Let γ＊（D） denote the twin domination number of digraph D and let Cm Cn denote the Cartesian product of C_m and C_n, the directed cycles of length m, n ≥ 2. In this paper, we determine the exact values： γ＊（C_2□C_n） = n; γ＊（C_3 □C_n） = n if n ≡ 0（mod 3）,otherwise, γ＊（C_3□C_n） = n ＋ 1; γ＊（C_4□C_n） = n ＋ n/2 if n ≡ 0, 3, 5（mod 8）, otherwise,γ＊（C_4□C_n） = n ＋ n/2 ＋ 1; γ＊（C_5□C_n） = 2n; γ＊（C_6□C_n） = 2n if n ≡ 0（mod 3）, otherwise,γ＊（C_6□C_n） = 2n ＋ 2.
文摘A subset S of V is called a k-connected dominating set if S is a dominating set and the induced subgraph S has at most k components.The k-connected domination number γck（G） of G is the minimum cardinality taken over all minimal k-connected dominating sets of G.In this paper,we characterize trees and unicyclic graphs with equal connected domination and 2-connected domination numbers.
文摘Wireless sensor networks(WSNs)are one of the most important improvements due to their remarkable capacities and their continuous growth in various applications.However,the lifetime of WSNs is very confined because of the delimited energy limit of their sensor nodes.This is the reason why energy conservation is considered the main exploration worry for WSNs.For this energy-efficient routing is required to save energy and to subsequently drag out the lifetime of WSNs.In this report we use the Ant Colony Optimization(ACO)method and are evaluated using the Genetic Algorithm(GA),based on the Detour non-split dominant set(GA)In this research,we use the energy efficiency returnee non-split dominating set(DNSDS).A set S⊆V is supposed to be a DNSDS of G when the graph G=(V,E)is expressed as both detours as well as a non-split dominating set of G.Let the detour non-split domination number be addressed asγ_dns(G)and is the minimum order of its detour non-split dominating set.Any DNSDS of orderγdns(G)is aγdns-set of G.Here,theγ_dns(G)of various standard graphs is resolved and some of its general properties are contemplated.A connected graph usually has an order n with detour non-split domination number as n or n–1 are characterized.Also connected graphs of order n≥4 and detour diameter D≤4 with detour non-split dominating number n or n−1 or n−2 are additionally portrayed.While considering any pair of positive integers to be specific a and b,there exists a connected graph G which is normally indicated as dn(G)=a,γ(G)=b andγdns(G)=a+b−2,hereγdns(G)indicates the detour domination number and dn(G)indicates the detour number of a graph.The time is taken for the construction and the size of DNSDS are considered for examining the performance of the proposed method.The simulation result confirms that the DNSDS nodes are energy efficient.
文摘The bondage number of γ f, b f(G) , is defined to be the minimum cardinality of a set of edges whose removal from G results in a graph G′ satisfying γ f(G′)> γ f(G) . The reinforcement number of γ f, r f(G) , is defined to be the minimum cardinality of a set of edges which when added to G results in a graph G′ satisfying γ f(G′)< γ f(G) . G.S.Domke and R.C.Laskar initiated the study of them and gave exact values of b f(G) and r f(G) for some classes of graphs. Exact values of b f(G) and r f(G) for complete multipartite graphs are given and some results are extended.
基金The NSF(11301450,61363020,11226294)of Chinathe Youth Science and Technology Education Project(2014731003)of Xinjiang Province
文摘Let γ^＊（D） denote the twin domination number of digraph D and let Di× D 2 denote the strong product of Di and D 2. In this paper, we obtain that the twin domination number of strong product of two directed cycles of length at least 2. Furthermore, we give a lower bound of the twin domination number of strong product of two digraphs, and prove that the twin domination number of strong product of the complete digraph and any digraph D equals the twin domination number of D.
基金Supported by the National Natural Science Foundation of China (Grant No. 71774078)。
文摘A function f:E(G)→{−1,1}is called a signed edge dominating function(SEDF for short)of G if f[e]=f(N[e])=Σ_( e′∈N[e])f(e′)≥1,for every edge e∈E(G).w(f)=Σ_(e∈E) f(e)is called the weight of f.The signed edge domination numberγs′(G)of G is the minimum weight among all signed edge dominating functions of G.In this paper,we initiate the study of this parameter for G a complete multipartite graph.We provide the lower and upper bounds ofγs′(G)for G a complete r-partite graph with r even and all parts equal.
文摘Let <img src="Edit_092a0db1-eefa-4bff-81a0-751d038158ad.png" width="58" height="20" alt="" /> be a graph. A function <img src="Edit_b7158ed5-6825-41cd-b7f0-5ab5e16fc53d.png" width="79" height="20" alt="" /> is said to be a Signed Dominating Function (SDF) if <img src="Edit_c6e63805-bcaa-46a9-bc77-42750af8efd4.png" width="135" height="25" alt="" /> holds for all <img src="Edit_bba1b366-af70-46cd-aefe-fc68869da670.png" width="42" height="20" alt="" />. The signed domination number <img src="Edit_22e6d87a-e3be-4037-b4b6-c1de6a40abb0.png" width="284" height="25" alt="" />. In this paper, we determine the exact value of the Signed Domination Number of graphs <img src="Edit_36ef2747-da44-4f9b-a10a-340c61a3f28c.png" width="19" height="20" alt="" /> and <img src="Edit_26eb0f74-fcc2-49ad-8567-492cf3115b73.png" width="19" height="20" alt="" /> for <img src="Edit_856dbcc1-d215-4144-b50c-ac8a225d664f.png" width="32" height="20" alt="" />, which is generalized the known results, respectively, where <img src="Edit_4b7e4f8f-5d38-4fd0-ac4e-dd8ef243029f.png" width="19" height="20" alt="" /> and <img src="Edit_6557afba-e697-4397-994e-a9bda83e3219.png" width="19" height="20" alt="" /> are denotes the k-th power graphs of cycle <img src="Edit_27e6e80f-85d5-4208-b367-a757a0e55d0b.png" width="21" height="20" alt="" /> and path <img src="Edit_70ac5266-950b-4bfd-8d04-21711d3ffc33.png" width="18" height="20" alt="" />.
基金Supported by Ningbo Institute of Technology, Zhejiang Univ. Youth Innovation Foundation and Zhejiang Provincial Natural Science Foundation( Y604167).
文摘The relations among the dominating number, independence number and covering number of hypergraphs are investigated. Main results are as follows：Dv（H）≤min{α≤（H）, p（H）, p（H）, T（H）}; De（H）≤min{v（H）, T（H）, p（H）}; DT（H） ≤αT（H）; S（H）≤ Dv （H） ＋ α（H）≤n; 2≤ Dv （H） ＋ T（H） ≤n; 2 〈 Dv （H） ＋ v（H）≤n/2 ＋ [n/r]; Dv （H） ＋ p（H） 〈_n;2≤De（H） ＋ Dv（H）≤n/2 ＋ [n/r];α（H） ＋ De（H）≤n;2 ≤ De（H） ＋ v（H）≤2[n/r]; 2 De（H） ＋ p（H）≤n-r ＋ 2.
文摘The study of minus paired domination of a graph G=(V,E) is initiated. Let SV be any paired dominating set of G , a minus paired dominating function is a function of the form f∶V→{-1,0,1} such that f(v)= 1 for v∈S, f(v)≤0 for v∈V-S , and f(N)≥1 for all v∈V . The weight of a minus paired dominating function f is w(f)=∑f(v) , over all vertices v∈V . The minus paired domination number of a graph G is γ - p( G )=min{ w(f)|f is a minus paired dominating function of G }. On the basis of the minus paired domination number of a graph G defined, some of its properties are discussed.
文摘Let G=(V,E) be a simple graph. For any real valued function f:V →R, the weight of f is f(V) = ∑f(v) over all vertices v∈V . A signed total dominating function is a function f:V→{-1,1} such that f(N(v)) ≥1 for every vertex v∈V . The signed total domination number of a graph G equals the minimum weight of a signed total dominating function on G . In this paper, some properties of the signed total domination number of a graph G are discussed.
基金Supported by the National Natural Science Foundation of China(Grant Nos.1136102411061014)the Jiangxi Provincial Science and Technology Project(Grant No.KJLD12067)
文摘Let G = （V,E） be a simple graph. For any real function g ： V →R and a subset S 包涵于V, we write g（S） = ∑v∈sg（v）. A function f ： V → [0,1] is said to be a fractional dominating function （FDF） of G if f（N[v]） ≥ 1 holds for every vertex v ∈ V（G）. The fractional domination number γf（G） of G is defined as γf（G） = min{f（V）｜f is an FDF of G }. The fractional total dominating function f is defined just as the fractional dominating function, the difference being that f（N（v）） ≥ 1 instead of f（N[v]）≥ 1. The fractional total domination number γ^0f（G） of G is analogous. In this note we give the exact values of γf（Cm× Pn） and γ^0f（Cm × Pn） for all integers m ≥ 3 and n ≥ 2.
文摘Let γ f(G) and γ~t f(G) be the fractional domination number and fractional total domination number of a graph G respectively. Hare and Stewart gave some exact fractional domination number of P n×P m (grid graph) with small n and m . But for large n and m , it is difficult to decide the exact fractional domination number. Motivated by this, nearly sharp upper and lower bounds are given to the fractional domination number of grid graphs. Furthermore, upper and lower bounds on the fractional total domination number of strong direct product of graphs are given.
基金Supported by the Natural Science Foundation of Jiangsu Province(Grant No.BK20151117)the Key Scientific Research Foundation of Higher Education Institutions of Henan Province(Grant No.15B110009)
文摘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： VUE→{-1,1}such that ∑y∈Nm（x）U{x}f（y） ≥1 for every element x ∈ V U E, where Nm （x） is the set of elements of V U E adjacent or incident to x. The weight of f isw（f）∑x∈VUEf（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.
