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 ...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].展开更多
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 numb...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.展开更多
Let G be a graph and k be a positive integer. We consider a game with two players Alice and Bob who alternate in coloring the vertices of G with a set of k colors. In every turn, one vertex will be chosen by one playe...Let G be a graph and k be a positive integer. We consider a game with two players Alice and Bob who alternate in coloring the vertices of G with a set of k colors. In every turn, one vertex will be chosen by one player. Alice’s goal is to color all vertices with the k colors, while Bob’s goal is to prevent her. The game chromatic number denoted by?χg(G), is the smallest k such that Alice has a winning strategy with k colors. In this paper, we determine the game chromatic number?χg of circulant graphs?Cn(1,2), , and generalized Petersen graphs GP(n,2), GP(n,3).展开更多
In the eternal dominating set problem, guards form a dominating set on a graph and at each step, a vertex is attacked. We consider the “all guards move” of the eternal dominating set problem. In which one guard has ...In the eternal dominating set problem, guards form a dominating set on a graph and at each step, a vertex is attacked. We consider the “all guards move” of the eternal dominating set problem. In which one guard has to move to the attacked vertex and all the remaining guards are allowed to move to an adjacent vertex or stay in their current position after each attack. If the new formed set of guards is still a dominating set of the graph then we successfully defended the attack. Our goal is to find the minimum number of guards required to eternally protect the graph. We call this number the m-eternal domination number and we denote it by . In this paper we find the eternal domination number of Jahangir graph Js,m for s=2,3 and arbitrary m. We also find the domination number for J3,m .展开更多
A coloring of G is d-distance if any two vertices at distance at most d from each other get different colors. The minimum number of colors in d-distance colorings of G is its d-distance chromatic number, denoted by χ...A coloring of G is d-distance if any two vertices at distance at most d from each other get different colors. The minimum number of colors in d-distance colorings of G is its d-distance chromatic number, denoted by χd(G). In this paper, we give the exact value of χd(G) (d = 1, 2), for some types of generalized Petersen graphs P(n, k) where k = 1, 2, 3 and arbitrary n.展开更多
文摘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].
文摘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.
文摘Let G be a graph and k be a positive integer. We consider a game with two players Alice and Bob who alternate in coloring the vertices of G with a set of k colors. In every turn, one vertex will be chosen by one player. Alice’s goal is to color all vertices with the k colors, while Bob’s goal is to prevent her. The game chromatic number denoted by?χg(G), is the smallest k such that Alice has a winning strategy with k colors. In this paper, we determine the game chromatic number?χg of circulant graphs?Cn(1,2), , and generalized Petersen graphs GP(n,2), GP(n,3).
文摘In the eternal dominating set problem, guards form a dominating set on a graph and at each step, a vertex is attacked. We consider the “all guards move” of the eternal dominating set problem. In which one guard has to move to the attacked vertex and all the remaining guards are allowed to move to an adjacent vertex or stay in their current position after each attack. If the new formed set of guards is still a dominating set of the graph then we successfully defended the attack. Our goal is to find the minimum number of guards required to eternally protect the graph. We call this number the m-eternal domination number and we denote it by . In this paper we find the eternal domination number of Jahangir graph Js,m for s=2,3 and arbitrary m. We also find the domination number for J3,m .
文摘A coloring of G is d-distance if any two vertices at distance at most d from each other get different colors. The minimum number of colors in d-distance colorings of G is its d-distance chromatic number, denoted by χd(G). In this paper, we give the exact value of χd(G) (d = 1, 2), for some types of generalized Petersen graphs P(n, k) where k = 1, 2, 3 and arbitrary n.
