کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419511 | 683825 | 2010 | 4 صفحه PDF | دانلود رایگان |
We extend the notion of a defensive alliance to weighted graphs. Let (G,w)(G,w) be a weighted graph, where GG is a graph and ww be a function from V(G)V(G) to the set of positive real numbers. A non-empty set of vertices SS in GG is said to be a weighted defensive alliance if ∑x∈NG(v)∩Sw(x)+w(v)≥∑x∈NG(v)−Sw(x)∑x∈NG(v)∩Sw(x)+w(v)≥∑x∈NG(v)−Sw(x) holds for every vertex vv in SS. Fricke et al. (2003) [3] have proved that every graph of order nn has a defensive alliance of order at most ⌈12n⌉. In this note, we generalize this result to weighted defensive alliances. Let GG be a graph of order nn. Then we prove that for any weight function ww on V(G)V(G), (G,w)(G,w) has a defensive weighted alliance of order at most ⌈12n⌉. We also extend the notion of strong defensive alliance to weighted graphs and generalize a result in Fricke et al. (2003) [3].
Journal: Discrete Applied Mathematics - Volume 158, Issue 18, 28 November 2010, Pages 2071–2074