Search

Let G be a connected graph with vertex set V , where the distance between two vertices is the length of a shortest path between them. A set S ⊆ V is [ 1 , 2 ] -resolving if each vertex of G is at most distance-two away from a vertex in S and, given a pair of distinct vertices not in S , either there is a vertex in S adjacent to exactly one member of the given pair, or there are two vertices in S each of which is distance-two from exactly one member of the given pair. The [ 1 , 2 ] -dimension of G is the minimum cardinality of a [ 1 , 2 ] -resolving set of G. In this paper, we study the [ 1 , 2 ] -dimension of graphs by proving that the [ 1 , 2 ] -dimension problem is an NP-complete problem, and determine the [ 1 , 2 ] -dimension of some classes of graphs, such as paths, cycles, and full k -ary trees. We also introduce a generalization of metric dimension of which the (original) metric dimension and the [ 1 , 2 ] -dimension, as well as other metric dimension variants in the literature, are special instances. [ABSTRACT FROM AUTHOR]

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]

All-to-all communication occurs in many important applications in parallel processing. In this paper, we study the all-to-all broadcast number (the shortest time needed to complete the all-to-all broadcast) of Cartesian product of graphs under the assumption that: each vertex can use all of its links at the same time, and each communication link is half duplex and can carry only one message at a unit of time. We give upper and lower bounds for the all-to-all broadcast number of Cartesian product of graphs and give formulas for the all-to-all broadcast numbers of some classes of graphs, such as the Cartesian product of two cycles, the Cartesian product of a cycle with a complete graph of odd order, the Cartesian product of two complete graphs of odd order, and the hypercube Q 2 n under this model. [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 ) . Given a graph G , an L ( 2 , 1 ) -labeling of G is a function f from the vertex set V ( G ) to the set of all nonnegative integers such that | f ( x ) − f ( y ) | ≥ 2 if d G ( x , y ) = 1 , and | f ( x ) − f ( y ) | ≥ 1 if d G ( x , y ) = 2 . A k - L ( 2 , 1 ) -labeling is an L ( 2 , 1 ) -labeling such that no label is greater than k . The L ( 2 , 1 ) -labeling number of G , denoted by λ ( G ) , is the smallest number k such that G has a k - L ( 2 , 1 ) -labeling. We study the L ( 2 , 1 ) -labeling numbers of subdivisions of graphs in this paper. We prove that λ ( G ( 3 ) ) = Δ ( G ) + 1 for any graph G with Δ ( G ) ≥ 4 , and show that λ ( G ( h ) ) = Δ ( G ) + 1 if Δ ( G ) ≥ 5 and h is a function from E ( G ) to N so that h ( e ) ≥ 3 for all e ∈ E ( G ) , or if Δ ( G ) ≥ 4 and h is a function from E ( G ) to N so that h ( e ) ≥ 4 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 , a defensive alliance of is a set of vertices satisfying the condition that for each , at least half of the vertices in the closed neighborhood of are in . A defensive alliance is called global if every vertex in is adjacent to at least one member of the defensive alliance . The global defensive alliance number of , denoted , is the minimum size around all the global defensive alliances of . In this paper, we present an efficient algorithm to determine the global defensive alliance numbers of trees, and further give formulas to decide the global defensive alliance numbers of complete -ary trees for . We also establish upper bounds and lower bounds for and , and show that the bounds are sharp for certain . [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]

Abstract: Given a graph and a vertex subset of , the broadcasting time with respect to , denoted by , is the minimum broadcasting time when using as the broadcasting set. And the -broadcasting number, denoted by , is defined by . Given a graph and two vertex subsets , of , define , , , and for all . For all , , the -radius of , denoted by , is defined as , . In this paper, we study the relation between the -radius and the -broadcasting numbers of graphs. We also give the -radius and the -broadcasting numbers of the grid graphs, and the -broadcasting numbers of the complete -partite graphs and the hypercubes. [Copyright &y& Elsevier]

Abstract: All-to-all communication occurs in many important applications in parallel processing. In this paper, we study the all-to-all broadcast number (the shortest time needed to complete the all-to-all broadcast) of graphs under the assumption that: each vertex can use all of its links at the same time, and each communication link is half duplex and can carry only one message at a unit of time. We give upper and lower bounds for the all-to-all broadcast number of graphs and give formulas for the all-to-all broadcast number of trees, complete bipartite graphs and double loop networks under this model. [Copyright &y& Elsevier]