Search

Let G be a connected graph, and let D (G) be the set of all dominating (multi)sets for G. For D 1 and D 2 in D (G) , we say that D 1 is single-step transferable to D 2 if there exist u ∈ D 1 and v ∈ D 2 , such that u v ∈ E (G) and D 1 − { u } = D 2 − { v }. We write D 1 ⟶ ∗ D 2 if D 1 can be transferred to D 2 through a sequence of single-step transfers. We say that G is k -transferable if D 1 ⟶ ∗ D 2 for any D 1 , D 2 ∈ D (G) with | D 1 | = | D 2 | = k. The transferable domination number of G is the smallest integer k to guarantee that G is l -transferable for all l ≥ k. We study the transferable domination number of graphs in this paper. We give upper bounds for the transferable domination number of general graphs and bipartite graphs, and give a lower bound for the transferable domination number of grids. We also determine the transferable domination number of P m × P n for the cases that m = 2 , 3 , or m n ≡ 0 (mod 6). Besides these, we give an example to show that the gap between the transferable domination number of a graph G and the smallest number k so that G is k -transferable can be arbitrarily large. [ABSTRACT FROM AUTHOR]

Given a graph G and a function h from E (G) to N , the h -subdivision of G , denoted by G (h) , is the graph obtained from G by replacing each edge u v in G with a path P : u x u v 1 x u v 2 ... x u v n − 1 v , where n = h (u v). When h (e) = c is a constant for all e ∈ E (G) , we use G (c) to replace G (h) . For a given graph G , an L (p , q) -labeling of G is a function f from the vertex set V (G) to the set of all nonnegative integers such that f (u) − f (v) ≥ p if d G (u , v) = 1 , and f (u) − f (v) ≥ q if d G (u , v) = 2. A k - L (p , q) -labeling is an L (p , q) -labeling such that no label is greater than k. The L (p , q) -labeling number of G , denoted by λ p , q (G) , is the smallest number k such that G has a k - L (p , q) -labeling. We study the L (p , q) -labeling numbers of subdivisions of graphs in this paper. We prove that λ p , q (G (3) ) = p + (Δ − 1) q when p ≥ 2 q and Δ > 2 p q , and show that λ p , q (G (h) ) = p + (Δ − 1) q when p ≥ 2 q and Δ ≥ 3 p q , where h is a function from E (G) to N so that h (e) ≥ 3 for all e ∈ E (G). [ABSTRACT FROM AUTHOR]

Abstract: Let be a graph and let be a positive integer. Consider the following two-person game which is played on : Alice and Bob alternate turns. A move consists of selecting an unlabeled vertex of and assigning it a number from satisfying the condition that, for all is labeled by the number previously, if , then , and if , then . Alice wins if all the vertices of are successfully labeled. Bob wins if an impasse is reached before all vertices in the graph are labeled. The game -labeling number of a graph is the least for which Alice has a winning strategy. We use to denote the game -labeling number of in the game Alice plays first, and use to denote the game -labeling number of in the game Bob plays first. In this paper, we study the game -labeling numbers of graphs. We give formulas for and , and give formulas for for those with . [Copyright &y& Elsevier]

Abstract: Given a graph and two positive integers with an -labeling of is a function from the vertex set to the set of all nonnegative integers such that if and if . A -labeling is an -labeling such that no label is greater than . The -labeling number of , denoted by is the smallest number such that has a -labeling. When considering the digraph , we use in place of . We study the -labeling number of a digraph in this paper. We find some relations between the -labeling number of a graph and an orientation of , and give some results for the -labeling numbers of -partite digraphs. We also study the -labeling numbers for those graphs for which the underlying graphs are paths, cycles or trees. [Copyright &y& Elsevier]