Search

LetG=(V, E) be a graph of ordernand letB(D) be the set of vertices inV∖Dthat have a neighbour in the setD. The differential of a setDis defined as ∂ (D)=|B(D)|−|D| and the differential of a graph to equal the maximum value of ∂(D) for any subsetDofV. In this paper we obtain several tight bounds for the differential of strong product graphs. In particular, we investigate the relationship between the differential of this type of product graphs and various parameters in the factors of the product. [ABSTRACT FROM PUBLISHER]

Abstract: In this paper, we obtain several tight bounds of the defensive -alliance number in the complement graph from other parameters of the graph. In particular, we investigate the relationship between the alliance numbers of the complement graph and the minimum and maximum degree, the domination number and the isoperimetric number of the graph. Moreover, we prove the NP-completeness of the decision problem underlying the defensive -alliance number. [Copyright &y& Elsevier]

Abstract: An offensive alliance in a graph is a set of vertices where for each vertex in its boundary the majority of vertices in ’s closed neighborhood are in . In the case of strong offensive alliance, strict majority is required. An alliance is called global if it affects every vertex in , that is, is a dominating set of . The global offensive alliance number is the minimum cardinality of a global offensive alliance in . An offensive alliance is connected if its induced subgraph is connected. The global-connected offensive alliance number, , is the minimum cardinality of a global-connected offensive alliance in . In this paper we obtain several tight bounds on and in terms of several parameters of . The case of strong alliances is studied by analogy. [Copyright &y& Elsevier]

Abstract: Let be a simple graph. For a nonempty set , and a vertex , denotes the number of neighbors has in . A nonempty set is a defensive -alliance in if . A defensive -alliance is called global if it forms a dominating set. The global defensive -alliance number of , denoted by , is the minimum cardinality of a defensive -alliance in . We study the mathematical properties of . [Copyright &y& Elsevier]

Abstract: Let be a simple graph of size and degree sequence . Let denote the line graph of . The aim of this work is to study mathematical properties of the alliance number, , and the global alliance number, , of the line graph of a simple graph. We show that . In particular, if is a -regular graph (), then , and if is a -semiregular bipartite graph, then . As a consequence of the study we compare and , and we characterize the graphs having . Moreover, we show that the global-connected alliance number of is bounded by , where denotes the diameter of , and we show that the global alliance number of is bounded by . The case of strong alliances is studied by analogy. [Copyright &y& Elsevier]

Abstract: An offensive alliance in a graph is a set of vertices where for every vertex v in its boundary it holds that the majority of vertices in v''s closed neighborhood are in S. In the case of strong offensive alliance, strict majority is required. An alliance S is called global if it affects every vertex in V\S, that is, S is a dominating set of Γ. The global offensive alliance number (respectively, global strong offensive alliance number ) is the minimum cardinality of a global offensive (respectively, global strong offensive) alliance in Γ. In this paper we obtain several tight bounds on and in terms of several parameters of Γ. [Copyright &y& Elsevier]

Let G be a graph with no isolated vertex. A function f : V (G) → { 0 , 1 , 2 } is a total { 2 } -dominating function on G if ∑ u ∈ N (v) f (u) ≥ 2 for every vertex v ∈ V (G). The total { 2 } -domination number of G , denoted by γ { 2 } , t (G) , is the minimum weight ω (f) = ∑ v ∈ V (G) f (v) among all total { 2 } -dominating functions on G. It is known that for any graph G with no isolated vertex, γ t (G) + 1 ≤ γ { 2 } , t (G) ≤ 2 γ t (G) , where γ t (G) represents the classical total domination number of G. In this paper, we first improve the previous lower bound, and as a consequence, we give necessary conditions for the graphs which satisfy this equality. Finally, we prove that any nontrivial tree T satisfies the equality in the upper bound, i.e., γ { 2 } , t (T) = 2 γ t (T). [ABSTRACT FROM AUTHOR]