Defensive -alliances in graphs

✍ Scribed by Juan A. Rodríguez-Velázquez; Ismael G. Yero; José M. Sigarreta

• Book ID: 104000507
• Publisher: Elsevier Science
• Year: 2009
• Tongue: English
• Weight: 412 KB
• Volume: 22
• Category: Article
• ISSN: 0893-9659
• DOI: 10.1016/j.aml.2008.02.012

✦ Synopsis

a b s t r a c t

Let G = (V, E) be a simple graph of order n and degree sequence

The defensive k-alliance number of G, denoted by a k (G), is defined as the minimum cardinality of a defensive k-alliance in G. We study the mathematical properties of a k (G). We show

, where µ is the algebraic connectivity of G and k ∈ {-δ n , . . . , δ 1 }. Moreover, we show that for every k, r ∈ Z such that -δ n ≤ k ≤ δ 1 and 0 ≤ r ≤ k+δn 2 , a k-2r (G) + r ≤ a k (G) and, as a consequence, we show that for every k ∈ {-δ n , . . . , 0}, a k (G) ≤ n+k+1 2 . In the case of the line graph L(G) of a simple graph G, we obtain bounds on a k (L(G)) and, as a consequence of the study, we show that for any δ-regular graph, δ > 0, and for every k ∈ {2(1 -δ), . . . , 0}, a k (L(G)) = δ + k 2 . Moreover, for any (δ 1 , δ 2 )-semiregular bipartite graph G, δ 1 > δ 2 , and for every k ∈ {2 -δ 1 -δ 2 , . . . , δ 1 -δ 2 }, a k (L(G)) = δ1+δ2+k 2 .