Roman Domination Number and Domination Number of a Tree

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.

On Graphs with Equal Connected Domination and 2-connected Domination Numbers

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.

Lower Bounds on the Majority Domination Number of Graphs

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.

An Upper Bound for Total Domination Number

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.

The Twin Domination Number of Strong Product of Digraphs

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.

The Generalization of Signed Domination Number of Two Classes of Graphs

Let be a graph. A function is said to be a Signed Dominating Function (SDF) if holds for all . The signed domination number . In this paper, we determine the exact value of the Signed Domination Number of graphs and for , which is generalized the known results, respectively, where and are denotes the k-th power graphs of cycle and path .

The Signed Domination Number of Cartesian Product of Two Paths

Let G be a finite connected simple graph with vertex set V(G) and edge set E(G). A function f:V(G) → {1,1} is a signed dominating function if for every vertex v∈V(G), the closed neighborhood of v contains more vertices with function values 1 than with −1. The signed domination number γs(G) of G is the minimum weight of a signed dominating function on G. In this paper, we calculate The signed domination numbers of the Cartesian product of two paths Pm and Pn for m = 3, 4, 5 and arbitrary n.

Total Domination number of Generalized Petersen Graphs

Generalized Petersen graphs are an important class of commonly used interconnection networks and have been studied . The total domination number of generalized Petersen graphs P(m,2) is obtained in this paper.

On the Signed Domination Number of the Cartesian Product of Two Directed Cycles

Let D be a finite simple directed graph with vertex set V(D) and arc set A(D). A function ?is called a signed dominating function (SDF) if ?for each vertex . The weight ?of f is defined by . The signed domination number of a digraph D is . Let Cm × Cn denotes the cartesian product of directed cycles of length m and n. In this paper, we determine the exact values of gs(Cm × Cn) for m = 8, 9, 10 and arbitrary n. Also, we give the exact value of gs(Cm × Cn) when m, ?(mod 3) and bounds for otherwise.

Independent Roman{2}-Domination in Trees

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.

A lower bound on the total signed domination numbers of graphs

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 .

On Signed Edge Total Domination Numbers of Graphs

Let G = （V,E） be a graph.A function f ： E → {-1,1} is said to be a signed edge total dominating function （SETDF） of G if e ∈N（e） f（e ） ≥ 1 holds for every edge e ∈ E（G）.The signed edge total domination number γ st （G） of G is defined as γ st （G） = min{ e∈E（G） f（e）｜f is an SETDF of G}.In this paper we obtain some new lower bounds of γ st （G）.

On the Characterization of Maximal Planar Graphs with a Given Signed Cycle Domination Number

Let G = （V, E） be a simple graph. A function f ： E → {＋1,-1} is called a signed cycle domination function （SCDF） of G if ∑e∈E（C） f（e） ≥ 1 for every induced cycle C of G. The signed cycle domination number of G is defined as γ′sc（G） = min{∑e∈E f（e）｜ f is an SCDF of G}. This paper will characterize all maxima] planar graphs G with order n ≥ 6 and γ′sc（G） =n.

Some Upper Bounds Related with Domination Number

For a simple and connected graph G,denote the domination number,the diameter,and the radius of G asβ(G),D(G),and r(G),respectively.In this paper,we solve two conjectures on the upper bounds ofβ(G)·D(G)andβ(G)+r(G),which are proposed by the computer system AutoGraphiX.Extremal trees which attain the upper bounds are also considered.

Characterization of Connected Graphs with Maximum Domination Number

Let G be a connected graph of order p, and let γ7(G) denote the domination number of G. Clearly, γ(G) ≤[p/2]. The aim of this paper is to characterize the graphs G that reaches this upper bound. The main results are as follows: (1) when p is even, γ(G) = p/2 if and only if either G C4 or G is the crown of a connected graph with p/2 vertices; (2) when p is odd, γ(G) = (p-1)/2 if and only if every spanning tree of G is one of the two classes of trees shown in Theorem 3.1.

A Lower Bound for the Algebraic Connectivity of a Graph in Terms of the Domination Number

We investigate how the algebraic connectivity of a graph changes by relocating a connected branch from one vertex to another vertex, and then minimize the algebraic connectivity among all connected graphs of order n with fixed domination number γ≤（n＋2）/3, and finally present a lower bound for the algebraic connectivity in terms of the domination number. We also characterize the minimum algebraic connectivity of graphs with domination number half their order.

Domination Number of Square of Cartesian Products of Cycles

A set ?is a dominating set of G if every vertex of ?is adjacent to at least one vertex of S. The cardinality of the smallest dominating set of G is called the domination number of G. The square G2 of a graph G is obtained from G by adding new edges between every two vertices having distance 2 in G. In this paper we study the domination number of square of graphs, find a bound for domination number of square of Cartesian product of cycles, and find the exact value for some of them.

On the 2-Domination Number of Complete Grid Graphs

A set D of vertices of a graph G = (V, E) is called k-dominating if every vertex v ∈V-D is adjacent to some k vertices of D. The k-domination number of a graph G, γk (G), is the order of a smallest k-dominating set of G. In this paper we calculate the k-domination number (for k = 2) of the product of two paths Pm × Pn for m = 1, 2, 3, 4, 5 and arbitrary n. These results were shown an error in the paper [1].

Bounds on Fractional Domination of Some Products of Graphs

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.

On Minus Paired-Domination in Graphs

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.