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.

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.

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.

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.

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.

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 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.

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.

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.

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 .

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].

关于图的连通DOMINATION的若干结果

设G是n阶连通图.γ_c(G),d_c(G),i(G)和ir(G)分别表示G图的连通Domination数,连通Domatic数,独立Domination数和Irredundance数,k(G)表示G的连通度.本文证明了下列结论. (1) 如n≥3,则i(G)+γ_c(G)≤n+[n/3]-2; (2) γ_c(G)≤4ir(G)-2; (3) γ_c(G)≤k(G)+1; (4) 如G≠K_n,则d_c(G)≤k(G). 此外,本文给出了满足等式γ_c(G)+γ_c(G)=n和γ_c(G)+γ_c(G)=n+1的图G的一个特征.

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.

Signed Total Domination in Graphs

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.

Ranking grey numbers based on dominance grey degrees

With respect to the decision making problems where a lot of fuzzy and grey information always exists in the real-life decision making information system methods as fuzzy mathematics, it is difficult for such uncertainty probability, and interval numbers to deal with. To this end, based on the thought and method of grey numbers, grey degrees and interval numbers, the concept of dominance grey degree is defined. And then a method of ranking interval grey numbers based on the dominance grey degree is proposed. After discussing the relevant properties, the paper finally uses an example to demonstrate the effectiveness and applicability of the model. The result shows that the proposed model can more accurately describe uncertainty decision making problems, and realize the total ordering process for multiple-attribute decision-making problems.

(d,m)-DOMINATING NUMBERS OF HYPERCUBE

This paper shows that the (d,m)-dominating number of the m-dimensional hypercube Q m(m≥4) is 2 for any integer d.[FK(W1*1。*2]m2[FK(W1*1。*2]+2≤d≤m.

Dominating Sets and Domination Polynomials of Square of Paths

Let G = (V, E) be a simple graph. A set S í V is a dominating set of G, if every vertex in V-S is adjacent to at least one vertex in S. Let be the square of the Path and let denote the family of all dominating sets of with cardinality i. Let . In this paper, we obtain a recursive formula for . Using this recursive formula, we construct the polynomial, , which we call domination polynomial of and obtain some properties of this polynomial.

图的笛卡儿积的Domination数

对某些图类证明了 Vizing 猜想.设 G 为任意一个图,若图 H 满足下列条件之一,则 y(G×H)≥y(G)y(H):①图 H 为 n-圈 C_n;②y(H)≤2;③y(H)=n,H 中至少含有 n-2条互不邻接的端线.

Edge-Vertex Dominating Sets and Edge-Vertex Domination Polynomials of Cycles

Let G = (V, E) be a simple graph. A set S E(G) is an edge-vertex dominating set of G (or simply an ev-dominating set), if for all vertices v V(G);there exists an edge eS such that e dominates v. Let denote the family of all ev-dominating sets of with cardinality i. Let . In this paper, we obtain a recursive formula for . Using this recursive formula, we construct the polynomial, , which we call edge-vertex domination polynomial of (or simply an ev-domination polynomial of ) and obtain some properties of this polynomial.

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.