Outer-independent Roman domination on graphs originates from the defensive strategy of Ancient Rome,which is that if any city without an army is attacked,a neighboring city with two armies could mobilize an army to su...Outer-independent Roman domination on graphs originates from the defensive strategy of Ancient Rome,which is that if any city without an army is attacked,a neighboring city with two armies could mobilize an army to support it and any two cities that have no army cannot be adjacent.The outer-independent Roman domination on graphs is an attractive topic in graph theory,and the definition is described as follows.Given a graph G=(V,E),a function f:V(G)→{0,1,2}is an outer-independent Roman dominating function(OIRDF)if f satisfies that every vertex v∈V with f(v)=0 has at least one adjacent vertex u∈N(v)with f(u)=2,where N(v)is the open neighborhood of v,and the set V0={v|f(v)=0}is an independent set.The weight of an OIRDF f is w(f)=∑_(v∈V)f(v).The value of minf w(f)is the outerindependent Roman domination number of G,denoted asγoiR(G).This paper is devoted to the study of the outer-independent Roman domination number of the Cartesian product of paths P_(n)□P_(m).With the help of computer,we find some recursive OIRDFs and then we present an upper bound ofγoiR(P_(n)□P_(m)).Furthermore,we prove the lower bound ofγoiR(P_(n)□P_(m))(n≤3)is equal to the upper bound.Hence,we achieve the exact value ofγoiR(P_(n)□P_(m))for n≤3 and the upper bound ofγoiR(P_(n)□P_(m))for n≥4.展开更多
Consider a graph G=(V,E).A perfect double Roman dominating function(PDRDF for short)is a function h:V→{0,1,2,3}that satisfies the condition∑_(y∈NG[x],h(y)≥1)h(y)=|{y∈NG(x):h(y)≥1}|+2 for any x∈V with h(x)≤1.Th...Consider a graph G=(V,E).A perfect double Roman dominating function(PDRDF for short)is a function h:V→{0,1,2,3}that satisfies the condition∑_(y∈NG[x],h(y)≥1)h(y)=|{y∈NG(x):h(y)≥1}|+2 for any x∈V with h(x)≤1.The weightω(h)of this function is∑_(y∈V)h(y).The perfect double Roman domination number(PDRD-number)of G,denoted byγ_(dR)^(p)(G),is defined as the minimum weight among all PDRDFs of G.This article presents a comprehensive analysis of the PDRD-number of connected cographs,demonstrating that it falls within the set{2,3,4,5,6}.Furthermore,it establishes that for any integer i≥7,there is a connected cograph G such that its PDRD-number is equal to i.展开更多
LetΩbe homogeneous of degree zero,integrable on S^(d−1) and have vanishing moment of order one,a be a function on R^(d) such that ∇a∈L^(∞)(R^(d)).Let T*_(Ω,a) be the maximaloperator associated with the d-dimensional...LetΩbe homogeneous of degree zero,integrable on S^(d−1) and have vanishing moment of order one,a be a function on R^(d) such that ∇a∈L^(∞)(R^(d)).Let T*_(Ω,a) be the maximaloperator associated with the d-dimensional Calder´on commutator defined by T*_(Ωa)f(x):=sup_(ε>0)|∫_(|x-y|>ε)^Ω(x-y)/|x-y|^(d+1)(a(x)-a(y))f(y)dy.In this paper,the authors establish bilinear sparse domination for T*_(Ω,a) under the assumption Ω∈L∞(Sd−1).As applications,some quantitative weighted bounds for T*_(Ω,a) are obtained.展开更多
The domination problem of graphs is an important issue in the field of graph theory.This paper mainly considers the Italian domination number of the strong product between two paths.By constructing recursive Italian d...The domination problem of graphs is an important issue in the field of graph theory.This paper mainly considers the Italian domination number of the strong product between two paths.By constructing recursive Italian dominating functions,the upper bound of its Italian domination number is obtained,and then a partition method is proposed to prove its lower bound.Finally,this paper yields a sharp bound for the Italian domination number of the strong product of paths.展开更多
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.展开更多
A path <i>π</i> = [<i>v</i><sub>1</sub>, <i>v</i><sub>2</sub>, …, <i>v</i><sub><em>k</em></sub>] in a graph <i>G&...A path <i>π</i> = [<i>v</i><sub>1</sub>, <i>v</i><sub>2</sub>, …, <i>v</i><sub><em>k</em></sub>] in a graph <i>G</i> = (<i>V</i>, <i>E</i>) is an uphill path if <i>deg</i>(<i>v</i><sub><i>i</i></sub>) ≤ <i>deg</i>(<i>v</i><sub><i>i</i>+1</sub>) for every 1 ≤ <i>i</i> ≤ <i>k</i>. A subset <i>S </i><span style="white-space:nowrap;"><span style="white-space:nowrap;">⊆</span></span> <i>V</i>(<i>G</i>) is an uphill dominating set if every vertex <i>v</i><sub><i>i</i></sub> <span style="white-space:nowrap;"><span style="white-space:nowrap;">∈</span> </span><i>V</i>(<i>G</i>) lies on an uphill path originating from some vertex in <i>S</i>. The uphill domination number of <i>G</i> is denoted by <i><span style="white-space:nowrap;"><i><span style="white-space:nowrap;"><i>γ</i></span></i></span></i><sub><i>up</i></sub>(<i>G</i>) and is the minimum cardinality of the uphill dominating set of <i>G</i>. In this paper, we introduce the uphill domination polynomial of a graph <i>G</i>. The uphill domination polynomial of a graph <i>G</i> of <i>n</i> vertices is the polynomial <img src="Edit_75fb5c37-6ef5-4292-9d3a-4b63343c48ce.bmp" alt="" />, where <em>up</em>(<i>G</i>, <i>i</i>) is the number of uphill dominating sets of size <i>i</i> in <i>G</i>, and <i><span style="white-space:nowrap;"><i><span style="white-space:nowrap;"><i>γ</i></span></i></span></i><i><sub>up</sub></i>(<i>G</i>) is the uphill domination number of <i>G</i>, we compute the uphill domination polynomial and its roots for some families of standard graphs. Also, <i>UP</i>(<i>G</i>, <em>x</em>) for some graph operations is obtained.展开更多
A dominating set D in a graph G is called an injective equitable dominating set (Inj-equitable dominating set) if for every , there exists such that u is adjacent to v and . The minimum cardinality of such a dominatin...A dominating set D in a graph G is called an injective equitable dominating set (Inj-equitable dominating set) if for every , there exists such that u is adjacent to v and . The minimum cardinality of such a dominating set is denoted by and is called the Inj-equitable domination number of G. In this paper, we introduce the injective equitable domination of a graph and study its relation with other domination parameters. The minimal injective equitable dominating set, the injective equitable independence number , and the injective equitable domatic number are defined.展开更多
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 be a simple graph with no isolated vertices. A set S of vertices of G is a total dominating set if every vertex of G is adjacent to some vertex in S . The total domination number of G , den...Let G be a simple graph with no isolated vertices. A set S of vertices of G is a total dominating set if every vertex of G is adjacent to some vertex in S . The total domination number of G , denoted by γ t (G) , is the minimum cardinality of a total dominating set of G . It is shown that if G is a graph of order n with minimum degree at least 3, then γ t (G)≤n/2 . Thus a conjecture of Favaron, Henning, Mynhart and Puech is settled in the affirmative.展开更多
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 ...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.展开更多
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.展开更多
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.展开更多
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.展开更多
图 G 的一个 Domination 染色是使得图 G 的每个顶点 v 控制至少一个色类(可能是自身的色类), 并且每一个色类至少被 G 中一个顶点控制的一个正常染色。 图 G 的 Domination 色数是图 G 的 Domination 染色所需最小的颜色数目,用 χdd(...图 G 的一个 Domination 染色是使得图 G 的每个顶点 v 控制至少一个色类(可能是自身的色类), 并且每一个色类至少被 G 中一个顶点控制的一个正常染色。 图 G 的 Domination 色数是图 G 的 Domination 染色所需最小的颜色数目,用 χdd(G) 表示。 本文研究了图 G 的 Domination 色数与图 G 通过某种操作得到图 G"的 Domination 色数之间的关系。展开更多
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.展开更多
We have introduced the total domination polynomial for any simple non isolated graph G in [7] and is defined by Dt（G, x） = ∑in=yt（G） dr（G, i） x＇, where dr（G, i） is the cardinality of total dominating sets of...We have introduced the total domination polynomial for any simple non isolated graph G in [7] and is defined by Dt（G, x） = ∑in=yt（G） dr（G, i） x＇, where dr（G, i） is the cardinality of total dominating sets of G of size i, and yt（G） is the total domination number of G. In [7] We have obtained some properties of Dt（G, x） and its coefficients. Also, we have calculated the total domination polynomials of complete graph, complete bipartite graph, join of two graphs and a graph consisting of disjoint components. In this paper, we presented for any two isomorphic graphs the total domination polynomials are same, but the converse is not true. Also, we proved that for any n vertex transitive graph of order n and for any v ∈ V（G）, dt（G, i） = 7 dt（V）（G, i）, 1 〈 i 〈 n. And, for any k-regular graph of order n, dr（G, i） = （7）, i 〉 n-k and d,（G, n-k） = （kn） - n. We have calculated the total domination polynomial of Petersen graph D,（P, x） = 10X4 ＋ 72x5 ＋ 140x6 ＋ 110x7 ＋ 45x8 ＋ [ 0x9 ＋ x10. Also, for any two vertices u and v of a k-regular graph Hwith N（u） ≠ N（v） and if Dr（G, x） = Dt（ H, x ）, then G is also a k-regular graph.展开更多
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 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.展开更多
文摘Outer-independent Roman domination on graphs originates from the defensive strategy of Ancient Rome,which is that if any city without an army is attacked,a neighboring city with two armies could mobilize an army to support it and any two cities that have no army cannot be adjacent.The outer-independent Roman domination on graphs is an attractive topic in graph theory,and the definition is described as follows.Given a graph G=(V,E),a function f:V(G)→{0,1,2}is an outer-independent Roman dominating function(OIRDF)if f satisfies that every vertex v∈V with f(v)=0 has at least one adjacent vertex u∈N(v)with f(u)=2,where N(v)is the open neighborhood of v,and the set V0={v|f(v)=0}is an independent set.The weight of an OIRDF f is w(f)=∑_(v∈V)f(v).The value of minf w(f)is the outerindependent Roman domination number of G,denoted asγoiR(G).This paper is devoted to the study of the outer-independent Roman domination number of the Cartesian product of paths P_(n)□P_(m).With the help of computer,we find some recursive OIRDFs and then we present an upper bound ofγoiR(P_(n)□P_(m)).Furthermore,we prove the lower bound ofγoiR(P_(n)□P_(m))(n≤3)is equal to the upper bound.Hence,we achieve the exact value ofγoiR(P_(n)□P_(m))for n≤3 and the upper bound ofγoiR(P_(n)□P_(m))for n≥4.
基金Supported by the National Natural Science Foundation Youth Fund of China(Grant No.11701059)The Chongqing Natural Science Foundation Innovation and Development Joint Fund(Municipal Education Commission)(Grant No.CSTB2022NSCQ-LZX0003)The Open Research Fund of Key Laboratory of Nonlinear Analysis&Applications(Central China Normal University),Ministry of Education,P.R.China。
文摘Consider a graph G=(V,E).A perfect double Roman dominating function(PDRDF for short)is a function h:V→{0,1,2,3}that satisfies the condition∑_(y∈NG[x],h(y)≥1)h(y)=|{y∈NG(x):h(y)≥1}|+2 for any x∈V with h(x)≤1.The weightω(h)of this function is∑_(y∈V)h(y).The perfect double Roman domination number(PDRD-number)of G,denoted byγ_(dR)^(p)(G),is defined as the minimum weight among all PDRDFs of G.This article presents a comprehensive analysis of the PDRD-number of connected cographs,demonstrating that it falls within the set{2,3,4,5,6}.Furthermore,it establishes that for any integer i≥7,there is a connected cograph G such that its PDRD-number is equal to i.
文摘LetΩbe homogeneous of degree zero,integrable on S^(d−1) and have vanishing moment of order one,a be a function on R^(d) such that ∇a∈L^(∞)(R^(d)).Let T*_(Ω,a) be the maximaloperator associated with the d-dimensional Calder´on commutator defined by T*_(Ωa)f(x):=sup_(ε>0)|∫_(|x-y|>ε)^Ω(x-y)/|x-y|^(d+1)(a(x)-a(y))f(y)dy.In this paper,the authors establish bilinear sparse domination for T*_(Ω,a) under the assumption Ω∈L∞(Sd−1).As applications,some quantitative weighted bounds for T*_(Ω,a) are obtained.
基金Supported by the National Natural Science Foundation of China(Grant No.11551002)The Natural Science Foundation of Qinghai Province(Grant No.2019-ZJ-7093).
文摘The domination problem of graphs is an important issue in the field of graph theory.This paper mainly considers the Italian domination number of the strong product between two paths.By constructing recursive Italian dominating functions,the upper bound of its Italian domination number is obtained,and then a partition method is proposed to prove its lower bound.Finally,this paper yields a sharp bound for the Italian domination number of the strong product of paths.
文摘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.
文摘A path <i>π</i> = [<i>v</i><sub>1</sub>, <i>v</i><sub>2</sub>, …, <i>v</i><sub><em>k</em></sub>] in a graph <i>G</i> = (<i>V</i>, <i>E</i>) is an uphill path if <i>deg</i>(<i>v</i><sub><i>i</i></sub>) ≤ <i>deg</i>(<i>v</i><sub><i>i</i>+1</sub>) for every 1 ≤ <i>i</i> ≤ <i>k</i>. A subset <i>S </i><span style="white-space:nowrap;"><span style="white-space:nowrap;">⊆</span></span> <i>V</i>(<i>G</i>) is an uphill dominating set if every vertex <i>v</i><sub><i>i</i></sub> <span style="white-space:nowrap;"><span style="white-space:nowrap;">∈</span> </span><i>V</i>(<i>G</i>) lies on an uphill path originating from some vertex in <i>S</i>. The uphill domination number of <i>G</i> is denoted by <i><span style="white-space:nowrap;"><i><span style="white-space:nowrap;"><i>γ</i></span></i></span></i><sub><i>up</i></sub>(<i>G</i>) and is the minimum cardinality of the uphill dominating set of <i>G</i>. In this paper, we introduce the uphill domination polynomial of a graph <i>G</i>. The uphill domination polynomial of a graph <i>G</i> of <i>n</i> vertices is the polynomial <img src="Edit_75fb5c37-6ef5-4292-9d3a-4b63343c48ce.bmp" alt="" />, where <em>up</em>(<i>G</i>, <i>i</i>) is the number of uphill dominating sets of size <i>i</i> in <i>G</i>, and <i><span style="white-space:nowrap;"><i><span style="white-space:nowrap;"><i>γ</i></span></i></span></i><i><sub>up</sub></i>(<i>G</i>) is the uphill domination number of <i>G</i>, we compute the uphill domination polynomial and its roots for some families of standard graphs. Also, <i>UP</i>(<i>G</i>, <em>x</em>) for some graph operations is obtained.
文摘A dominating set D in a graph G is called an injective equitable dominating set (Inj-equitable dominating set) if for every , there exists such that u is adjacent to v and . The minimum cardinality of such a dominating set is denoted by and is called the Inj-equitable domination number of G. In this paper, we introduce the injective equitable domination of a graph and study its relation with other domination parameters. The minimal injective equitable dominating set, the injective equitable independence number , and the injective equitable domatic number are defined.
文摘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 be a simple graph with no isolated vertices. A set S of vertices of G is a total dominating set if every vertex of G is adjacent to some vertex in S . The total domination number of G , denoted by γ t (G) , is the minimum cardinality of a total dominating set of G . It is shown that if G is a graph of order n with minimum degree at least 3, then γ t (G)≤n/2 . Thus a conjecture of Favaron, Henning, Mynhart and Puech is settled in the affirmative.
基金The NSF(11271365)of Chinathe NSF(BK20151117)of Jiangsu Province
文摘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.
基金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.
文摘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.
基金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.
文摘图 G 的一个 Domination 染色是使得图 G 的每个顶点 v 控制至少一个色类(可能是自身的色类), 并且每一个色类至少被 G 中一个顶点控制的一个正常染色。 图 G 的 Domination 色数是图 G 的 Domination 染色所需最小的颜色数目,用 χdd(G) 表示。 本文研究了图 G 的 Domination 色数与图 G 通过某种操作得到图 G"的 Domination 色数之间的关系。
基金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.
文摘We have introduced the total domination polynomial for any simple non isolated graph G in [7] and is defined by Dt（G, x） = ∑in=yt（G） dr（G, i） x＇, where dr（G, i） is the cardinality of total dominating sets of G of size i, and yt（G） is the total domination number of G. In [7] We have obtained some properties of Dt（G, x） and its coefficients. Also, we have calculated the total domination polynomials of complete graph, complete bipartite graph, join of two graphs and a graph consisting of disjoint components. In this paper, we presented for any two isomorphic graphs the total domination polynomials are same, but the converse is not true. Also, we proved that for any n vertex transitive graph of order n and for any v ∈ V（G）, dt（G, i） = 7 dt（V）（G, i）, 1 〈 i 〈 n. And, for any k-regular graph of order n, dr（G, i） = （7）, i 〉 n-k and d,（G, n-k） = （kn） - n. We have calculated the total domination polynomial of Petersen graph D,（P, x） = 10X4 ＋ 72x5 ＋ 140x6 ＋ 110x7 ＋ 45x8 ＋ [ 0x9 ＋ x10. Also, for any two vertices u and v of a k-regular graph Hwith N（u） ≠ N（v） and if Dr（G, x） = Dt（ H, x ）, then G is also a k-regular graph.
文摘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 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.
