Search

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]