Sobre Alianças Defensivas em Grafos
Rommel Melgaço Barbosa,
Elisângela Silva Dias,
Instituto de Informática, UFG,
Caixa Postal 131, Campus II, CEP: 74001-970, Goiânia, GO
E-mail: {rommel, elisangela}@inf.ufg.br
Resumo: Uma aliança defensiva no grafo G = (V, E) é um conjunto de vértices S ⊆ V satisfazendo a condição de que todo vértice v ∈ S tem no máximo um vizinho a mais em V − S que em
S. Devido a este tipo de aliança, os vértices em S juntam para se defenderem dos vértices em
V − S. Um conjunto seguro S ⊆ V no grafo G = (V, E) é um conjunto no qual todo subconjunto
não-vazio pode ser defendido com sucesso de um ataque, sob as definições apropriadas de “ataque” e “defesa”. Apresentamos aqui os conceitos para o entendimento das alianças em grafos,
junto com uma variedade de tipos de alianças e seus respectivos números, e mostramos novos
resultados sobre propriedades de alianças em grafos grade, ciclo, roda, caminho e grafo infinito
com relação ao número da aliança defensiva global, ao número da aliança defensiva forte global
e ao conjunto seguro de tais grafos.
Palavras-chave: Alianças em grafos, aliança defensiva, conjunto seguro.
1
Introdução
Denotamos por G = (V, E) um grafo tendo o conjunto de vértices V e o conjunto de arestas E.
Se |V | = n e |E| = m, dizemos que G é de ordem n e tamanho m. Para qualquer vértice v ∈ V ,
a vizinhança aberta de um vértice v é o conjunto N (v) = {u : uv ∈ E}, enquanto a vizinhança
fechada de v é o conjunto N [v] = N (v) ∪ {v}. As vizinhanças aberta e fechada do conjunto de
vértices S ⊆ V são definidas como segue: N (S) = ∪v∈S N (v) e N [S] = N (S) ∪ S. Similarmente,
para um conjunto S, a fronteira de S é o conjunto ∂S = N [S] − S.
Um subgrafo de G = (V, E) é um grafo G0 = (V 0 , E 0 ) tal que V 0 ⊆ V e E 0 ⊆ E. G0 é um
subgrafo prório se G0 6= G. Se G0 for um subgrafo de G que contém todas as arestas vw ∈ E
com (v, w) ∈ V 0 , então G0 é um subgrafo induzido de G. Para um subconjunto não-vazio S ⊆ V ,
denotamos por hSi o subgrafo de G induzido por S.
Dizemos que um conjunto S ⊆ V é um conjunto dominante se N [S] = V , ou seja, S ∪ ∂S =
V . O número de dominação, denotado por γ(G), é a cardinalidade mı́nima de um conjunto
dominante, ou seja, é o tamanho do menor conjunto dominante minimal de um grafo. Um
conjunto S é um conjunto dominante total ou conjunto dominante aberto se N (S) = V ou,
equivalentemente, se para todo v ∈ V , existe um u ∈ S, u 6= v, tal que u é adjacente a v.
Em um conjunto dominante total, cada vértice é adjacente a outro vértice de S, incluindo os
próprios vértices de S, isto é, nenhum vértice de S é um vértice isolado em hSi. O número
de dominação total, denotado por γt (G), é a cardinalidade mı́nima de um conjunto dominante
dominante total.
O tamanho do menor ciclo no grafo G é chamado cintura de G e é denotado por cintura(G).
Um grafo sem ciclos tem uma cintura de comprimento infinito. Note que, por definição, um
ciclo Cn de tamanho cintura(G) não contém quaisquer cordas, isto é, arestas entre dois vértices
não-consecutivos em Cn . Assim, por lcc(G) entenda que é o tamanho máximo de um ciclo sem
corda em um grafo G.
673
O problema de alianças em grafos foi primeiramente proposto por Kristiansen, Hedetniemi e
Hedetniemi [6]. Posteriormente, Fricke, Lawson, Haynes, Hedetniemi e Hedetniemi [3] estudaram
alianças defensivas em grafos. Em 2007, Brigham, Dutton e Hedetniemi [1] estudaram segurança
em grafos. Recentemente, Dutton [2] estudou os números dos conjuntos seguros e Rodrı́guezVelazquez, Yero e Sigarreta [10] estudaram a k-aliança defensiva, que é uma generalização para
aliança defensiva.
Na seção 2, apresentamos as definições de alianças defensivas em grafos e algumas de suas
variações, como alianças defensivas fortes, alianças defensivas globais e conjuntos seguros. Na
seção 3, exibimos uma tabela com resultados já existentes para algumas classes de grafos e
provamos novos resultados sobre alianças defensivas. Na seção 4, finalizamos o artigo com
algumas observações.
2
Alianças em Grafos
De forma bem simples, uma aliança é um conjunto de vértices que tem alguma propriedade
coletiva. Entretanto, como no mundo real, há diferentes tipos de alianças e definiremos alguns
deles a seguir.
Definição 1 Um conjunto não-vazio de vértices S ⊆ V é chamado uma aliança defensiva se e
somente se para todo v ∈ S, |N [v] ∩ S| ≥ |N [v] − S|, ou seja, para todo vértice v ∈ S, v tem no
máximo um vizinho a mais em V − S que em S.
Definição 2 Uma aliança defensiva é chamada forte se para todo vértice v ∈ S, |N [v] ∩ S| >
|N [v]−S|, ou seja, a inequação é estrita. Neste caso, dizemos que todo vértice em S é fortemente
defendido.
Definição 3 Uma aliança defensiva (forte) S é chamada crı́tica se nenhum subconjunto próprio
de S é também uma aliança defensiva (forte).
Definição 4 O número da aliança defensiva, denotado por a(G), é a cardinalidade mı́nima de
qualquer aliança defensiva crı́tica de G e o número da aliança defensiva forte, denotado por
â(G), é a cardinalidade mı́nima de qualquer aliança defensiva forte crı́tica de G.
Definição 5 O número superior da aliança defensiva global, denotado por A(G), é igual à
cardinalidade máxima de uma aliança defensiva crı́tica de G e Â(G) é a cardinalidade máxima
de uma aliança defensiva forte crı́tica de G.
Definição 6 Uma aliança defensiva é chamada global se ela afeta todo vértice em V − S, isto
é, todo vértice em V − S é adjacente a pelo menos um membro da aliança S. Neste caso, S é
um conjunto dominante. O número da aliança defensiva global, denotado por γa (G), é igual à
cardinalidade mı́nima de uma aliança defensiva global em G e γâ (G) é a cardinalidade mı́nima
de uma aliança defensiva forte global de G. Um conjunto S ⊆ V que é uma aliança defensiva
global de cardinalidade γa (G) é chamado conjunto-γa (G).
Definição 7 Dizemos que um conjunto S ⊆ V é seguro quando |N [X] ∩ S| ≥ |N [X] − S|, para
todo X ⊆ S. Intuitivamente, um conjunto é seguro se todo subconjunto não-vazio seu pode ser
defendido com sucesso de um ataque (sob as definições apropriadas de “ataque” e “defesa” que
introduziremos mais adiante).
Há várias maneiras de definir como um conjunto é atacado e defendido. Adotaremos aqui a
definição utilizada por Brigham, Dutton e Hedetniemi [1] a qual assume que um agressor u (um
membro de N [X]−S) pode atacar somente um único vértice de X em um determinado momento,
mesmo que u seja vizinho de vários vértices de X. Além disso, um defensor v (um membro de
674
N [X] ∩ S) pode impedir, de cada vez, somente um agressor dos vértices de N [X] ∩ S. Observe
que um defensor v necessita somente estar em S e não necessariamente em X. A definição formal
segue.
Definição 8 (Dutton [2])
(i) Seja G = (V, E) um grafo. Para qualquer S = {s1 , s2 , ..., sk } ⊆ V um ataque em S são
quaisquer k conjuntos A = {A1 , A2 , ..., Ak } mutuamente disjuntos para os quais Ai ⊆
N [si ] − S, 1 ≤ i ≤ k. Uma defesa de S são quaisquer conjuntos D = {D1 , D2 , ..., Dk }
mutuamente disjuntos para os quais Di ⊆ N [si ] ∩ S, 1 ≤ i ≤ k. Um ataque de A é
defensável se existe uma defesa D tal que |Di | ≥ |Ai | para 1 ≤ i ≤ k.
(ii) O conjunto S é seguro se e somente se todo ataque em S é defensável.
Definição 9 Um conjunto seguro S ⊆ V é crı́tico se nenhum subconjunto próprio de S é seguro.
Sendo assim, s(G) é a cardinalidade mı́nima de um conjunto seguro crı́tico de G. Um conjunto
seguro de cardinalidade s(G) é chamado conjunto-s(G) ou simplesmente conjunto-s.
3
Resultados Obtidos
Nesta seção, apresentamos novos resultados obtidos para os números das alianças defensivas
globais, defensivas fortes globais e para o número de segurança. Para isso, começamos fazendo
algumas observações quanto a esses números em diversas classes de grafos.
Como vemos na Tabela 1, o número da aliança defensiva em caminhos, grafos estrelas,
árvores, grafos 1-regular é 1, pois um vértice final nestes grafos forma uma aliança defensiva.
Segundo Shafique [7], a(G) ≤ â(G) ≤ Â(G), a(G) ≤ A(G), a(G) ≤ γa (G) e â(G) ≤ γâ (G).
O fato que A(Pn ) = Â(Pn ) = 2, para n ≥ 4, segue da observação que em um caminho,
quaisquer dois vértices adjacentes, em que nenhum deles é um vértice final, formam uma aliança
defensiva (forte) crı́tica. Visto que qualquer aliança defensiva (forte) crı́tica S deve induzir
um subgrafo conexo, as únicas alianças possı́veis são elas próprias caminhos. Mas visto que
elas deveriam conter dois vértices adjacentes, S não poderia ser crı́tica se conter mais que dois
vértices. O mesmo raciocı́nio aplica-se para a observação que A(Cn ) = Â(Cn ) = 2, para n ≥ 3,
e para grafos 3-regulares, onde novamente a maior aliança defensiva (forte) crı́tica consiste de
dois vértices adjacentes. Em um grafo 3-regular, quaisquer dois vértices adjacentes formam uma
aliança defensiva. Dessa forma, nenhuma aliança crı́tica maior é possı́vel e A(G) = 2.
Na roda Wn , temos que a(Wn ) = 2, pois dois vértices adjacentes no ciclo da roda formam
uma aliança defensiva.
Observamos que um ciclo sem corda qualquer em um grafo 3-regular ou no grafo 4-regular
forma uma aliança defensiva forte crı́tica, ou seja, o número da aliança defensiva é cintura(G).
Dessa forma, segue que em um grafo G 3-regular, Â(G) ≥ lcc(G). Mas Â(G) ≤ lcc(G), visto que
uma aliança defensiva forte crı́tica S qualquer em um grafo 3-regular G, que tem cardinalidade
maior que lcc(G), deve necessariamente conter um ciclo em hSi. Visto que o menor ciclo em hSi
é uma aliança defensiva forte crı́tica, segue que hSi próprio
deve induzir um ciclo sem corda.
n
Para um grafo completo, temos que a(Kn ) = 2 , pois precisamos de pelo menos metade
dos vértices do grafos para ter uma
aliança defensiva, visto que cada vértice tem n − 1 vizinhos
no grafo. Temos que â(Kn ) = n2 + 1, pois precisamos de um vértice a mais em S que em ∂S.
No grafo grade Gm,n , o número da aliança defensiva é 1 se o mı́nimo entre m e n é 1, ou
seja, existe um vértice final e este vértice será uma aliança defensiva. Caso o mı́nimo seja 2,
o número da aliança defensiva é 2, pois dois vértices adjacentes na grade formam uma aliança
defensiva.
Foi realizada uma revisão bibliográfica a respeito do assunto e a Tabela 1 provê uma visão
geral dos resultados anteriormente estabelecidos para a(G), â(G), γa (G), γâ (G) e s(G).
675
676
2 [6]
cintura(G) [6]
Kn
G
Gm,n
1, se min{m, n} = 1; [6]
2, se min{m, n} ≥ 2; [6]
n
[6]
δ 2
n − 2 = a(G) ≤ n2 [3]
2, se min{m, n} < 3; [6]
3, se min{m, n} = 3; [6]
4, se min{m,
n n} ≥ 4.[6]
+ 1 [6]
δ 2
n − 2 = â(G) ≤ n2 + 1 [3]
√
2n
3
[4, 8]
k(k−1)
2
[2]
min{m, n, 3} [1]
s(G) ≤
s(G)
1 [1]
2 [1]
2n [1]
2 [1]
?
1 [1]
?
?
?
?
?
1 [1]
2, se G contém K4 ; [1]
3, se G contém K2,3 ; [1]
cintura(G), caso c.[1]
?
?
2
n
[4]
2 [1] δ+1 δ
√
n ≤ γâ ≤ n − 2 [4] 2 ≤ s ≤ n − 2δ [1]
n+1 2
[4]
≤ γa (G) ≤ n − 2δ [4]
n+1 ?
?
≤ γa (L(G))[9]
≤ γâ (G) [4, 8]
γâ (G) ≤ 2n
3 [4, 8]
?
n
2
?
2m
δ1 +δ2 +1
γa (G) ≤ 2n
3 [4, 8]
?
m
≤ γa (G) ≤
4n+1−1
2
l
n
3
Tabela 1: Visão geral sobre os números das alianças de algumas classes de grafos.
a(G)
â(G)
γâ (G)
γa (G)
1 [6]
2, n ≥ 3 [6]
γt (Pn ) = n2 + n4 − n4 , n ≥ 2 [4] γt (Pn ), n ≥ 3 [4]
2 [6]
2,
γt (Cn ), n ≥ 3, exc. n ≡ 2(mod4) [4] γt (Cn ) [4], n ≥ 3 [4]
nn ≥ 3 [6]
r s 2 [6]
r s2 + 1 [6]
r s ?
r ? s +
,
+
,
+
,
2
≤
r
≤
s
[4]
2
≤
r
≤
s
[4]
se
r,
s
≥
2
[4]
2
2
2
2
r−1 2 s−12 r 2 +
s 2 [4]
1 [6]
?
+
+
+
se
r,
s
≥
1
[4]
2,
2
2
2
2 + 2 [4]
n+2
n+2
3n
1 [6]
â(T ) ≤ |V (T )| [5]
≤
γ
(T
)
≤
,
n
≥
4
≤
γ
(T
) ≤ 3n
[4]
a
â
4
5
3
4 [4]
1 [6]
2 [6]
?
?
2 [6]
2 [6]
?
?
2 [6]
∞ [6]
?
?
∞ [6]
∞ [6]
∞ [6]
∞ [6]
2 [6]
∞ [6]
?
?
1 [6]
2 [6]
1 [6]
2 [6]
4-reg.
cintura(G) [6]
cintura(G) [6]
5-reg. l
cintura(G)
?
[6]
l
m
m
δn +δn−1 −1
δn +δn−1
L(G)
≤ a(L(G)) ≤ δ1 [9]
≤ â(L(G)) ≤ δ1 [9]
2
2
3-reg.
Classe
Pn
Cn
Wn
Kr,s
Sr,s
T
P1,∞
P∞,∞
T2,∞
T3,∞
G∞,∞
1-reg.
Haynes, Hedetniemi e Henning [4] estudaram alianças defensivas globais para algumas classes
de grafos. Visto que não foi estudado para a classe de grafos grade, mostramos no próximo
teorema o limite superior exato para γa (Gm,n ).
Teorema 1
Seja G=(V,E) um grafo grade Gm,n , para m, n ≥ 3, m ≥ n, e x ∈ N.
 mn
 3 , se m = 3x ou n = 3x;
m
γa (Gm,n ) =
3 × n, se m = 3x + 2
 m
3 × n − 2, se m = 3x + 1;
Prova. Seja S um conjunto-γa (Gm,n ). Para ter uma aliança defensiva global em um grafo
grade com m ≥ 3, será necessário incluir em S os vértices de pelo menos uma linha da grade.
Para cobrir todos os vértices do grafo, de forma eficiente, se a quantidade de linhas ou colunas
é divisı́vel por 3, tomam-se ou as linhas ou as colunas 3 a 3, sendo a linha/coluna central
pertencente a S, e tem-se um conjunto dominante eficiente de cardinalidade mn
3 , que é uma
aliança defensiva global.
Se não temos um múltiplo de 3, m ≥ n e m mod n = 2, ainda
m é possı́vel ter uma dominação
eficiente. Se as linhas são divididas 3 a 3, incluindo em S os 3 × n vértices, restarão ainda 2
linhas. Considere estas as últimas linhas da grade. Para cobrir estas duas linhas, será necessário
incluir também em S os vértices da última linha
dominam a si mesmos e os vértices
que
m da linha
×
n
+
n
vértices
anterior. O conjunto S passa, então, a conter m
que
é
igual
a
3
3 × n.
Se m mod n = 1, ao serem divididas 3 a 3 as primeiras linhas,
somente
uma
delas
não estará
m
dominada. Neste caso, é necessário incluir em S, além dos 3 × n vértices, mais n − 2 vértices
da última linha, já que não será necessário incluir os vértices dos extremos, de grau dois, que
serão dominados por seus vizinhos da mesma linha. Neste caso, não temos uma dominação
eficiente.
Kristiansen,
Hedetniemi e Hedetniemi [6] provaram que a(Cn ) = â(Pn ) = â(Cn ) = a(Wn ) =
2 e â(Wn ) = n2 + 1. Dessa prova, mostramos a proposição seguinte para conjuntos seguros.
Proposição 1
Para um ciclo Cn , roda Wn e caminho Pn qualquer,
(i) s(Pn ) = 1.
(ii) s(Cn ) = 2.
(iii) s(Wn ) = 3.
Prova.
(i) Um vértice final no caminho Pn é um conjunto seguro. Visto que ele tem apenas um
vizinho e só existe o próprio vértice como subconjunto X ⊆ S, ele também é um conjunto
seguro.
(ii) Quaisquer dois vértices adjacentes em Cn constituem um conjunto seguro. Isso porque
todo vértice em Cn tem grau dois. Sendo assim, cada vértice de Cn em S terá um vértice
em ∂S. Dessa forma, só existem três subconjuntos a considerar: {x}, {y} e {x, y}. Os
subconjuntos unitários {x} e {y} só têm um vértice adjacente em Cn , que não está em
S, satisfazendo a condição de aliança defensiva e conjunto seguro. O subconjunto {x, y}
tem dois vizinhos em S e dois vizinhos em ∂S, também satisfazendo a condição de aliança
defensiva e conjunto seguro. Portanto, s(Cn ) = 2.
677
(iii) Quaisquer três vértices adjacentes no ciclo da roda Wn constituem um conjunto seguro,
visto que cada vértice tem grau três, sendo um dos vizinhos o vértice central (de grau
n), um vértice em S e um vértice em ∂S. Assim, S = {x, y, z} é uma aliança defensiva.
Então, só existem seis subconjuntos a considerar: (a) três subconjuntos unitários {x}, {y}
e {z}, que têm dois vizinhos em S e dois em ∂S; (b) {x, y}, em que |NS ({x, y})| = 3 e
|NV −S ({x, y})| = 2, sendo que existe um vértice z ∈ S; (c) {y, z}, idem (b); (d) {x, y, z},
em que |NS ({x, y, z})| = |NV −S ({x, y, z})| = 3. Portanto, S é um conjunto seguro. Não
existe s(Wn ) < 3, visto que todo subconjunto de S deve ser seguro. Suponha que s(Wn ) =
1, então S não é uma aliança defensiva e, portanto, não é um conjunto seguro. Suponha
que s(Wn ) = 2, então existem dois vértices adjacentes x e y que estão em S. Dessa
forma, temos 3 possı́veis subconjuntos: {x}, {y} e {x, y}. Assim, os subconjuntos {x},
{y} satisfazem a condição de aliança defensiva e de conjunto seguro, mas |NS ({x, y})| = 2 e
|NV −S ({x, y})| = 3, não satisfazendo a condição de conjunto seguro. Portanto, s(Wn ) ≥ 3.
Kristiansen, Hedetniemi e Hedetniemi [6] provaram que para um caminho infinito a(P∞,∞ ) =
â(P∞,∞ ) = 2 e também que para uma grade infinita a(G∞,∞ ) = â(G∞,∞ ) = 4. Assim, mostramos a proposição seguinte para grafos infinitos.
Proposição 2
(i) Para um caminho infinito P∞,∞ , γa (P∞,∞ ) = γâ (P∞,∞ ) = ∞
(ii) Para uma grade infinita G∞,∞ , γa (G∞,∞ ) = γâ (G∞,∞ ) = ∞.
(iii) Para uma árvore binária infinita com raiz T2,∞ , γa (T2,∞ ) = γâ (T2,∞ ) = ∞.
(iv) Para uma árvore ternária infinita com raiz T3,∞ , γa (T3,∞ ) = γâ (T3,∞ ) = ∞.
Prova.
(i) Visto que uma aliança defensiva global é um conjunto dominante, tal conjunto necessitaria
de pelo menos metade dos vértices de P∞,∞ . Nenhum subconjunto conexo de vértices S
em P∞,∞ pode ser uma aliança defensiva global, visto que em tal subconjunto S o subgrafo
induzido hSi deveria necessariamente ter ou um vértice final. Dessa forma, γa (P∞,∞ ) =
γâ (P∞,∞ ) não é finito.
(ii) Similarmente ao item (i), não é possı́vel ter um conjunto S finito.
(iii) Para árvores, um subconjunto S que é uma aliança defensiva global deve ter um vértice
final. Como a árvore é infinita, não tem tal vértice e γa (T2,∞ ) = γâ (T2,∞ ) = ∞.
(iv) Idem item (iii).
4
Conclusões
Apresentamos novos resultados para grafos grade, ciclo, roda, caminho e grafo infinito com
relação a γa (G), γâ (G) e s(G). Também foi realizado um estudo sobre alianças em grafos,
com ênfase em uma variação denominada aliança defensiva em grafos. Para tal conceito, foram
apresentadas variações sobre a definição original, como conjuntos seguros, e resultados teóricos
678
que se referem às propriedades das alianças em grafos, bem como limites para algumas classes
de grafos.
Observamos que várias propriedades matemáticas das alianças em grafos foram estudadas
desde o surgimento deste conceito, em 2003, até hoje. Portanto, apresentamos os resultados
teóricos que já foram obtidos na Tabela 1, que também nos mostra os parâmetros que ainda
podem ser estudados, sendo problemas em aberto.
A pesquisa em alianças em grafos ainda está muito incipiente e existem vários tipos de
alianças e propriedades a serem estudadas. Pode-se propor ainda a aplicação dos conceitos em
áreas práticas da ciência da computação ou em outras áreas como quı́mica, biologia, entre outras.
Quanto a conjuntos seguros, temos as seguintes questões em aberto:
(i) Determinar limites exatos gerais para o número de segurança de um grafo permanece como
uma interessante área de pesquisa. Em particular, não se conhece limite superior exato,
em função do número n de vértices, para todos os grafos.
é um limite superior para um grafo G qualquer tendo n vértices.
(ii) Saber se n+1
2
(iii) Defina a menor cardinalidade de um conjunto seguro dominante como sendo γse (G).
Quando γse (G) = s(G)?
(iv) Determinar, dado um conjunto não-seguro S, se ele contém um subconjunto seguro.
Referências
[1] R. C. Brigham, R. D. Dutton e S.T. Hedetniemi, Security in Graphs, Discrete Applied
Mathematics, 155 (2007) 1708-1714.
[2] R. D. Dutton, On a Graph’s Security Number, Discrete Applied Mathematics, 309 (2009)
4443-4447.
[3] G. H. Fricke, L. M. Lawson, T. W. Haynes, S. M. Hedetniemi e S. T. Hedetniemi, A Note
on Defensive Alliances in Graphs, Bulletin of the ICA., 38 (2003) 37-41.
[4] T. W. Haynes, S. T. Hedetniemi e M. A. Henning, Global Defensive Alliances in Graphs,
Eletron. J. Combin., 10 (2003) 139-146.
[5] Cheng-Ju Hsua, Fu-HsingWang e Yue-LiWang, Global Defensive Alliances in Star Graphs,
Discrete Applied Mathematics, 157 (2009) 1924-1931.
[6] Kristiansen, Petter. and Hedetniemi, Sandra. and Hedetniemi, Stephen T., Alliances in
Graphs, J. Combin. Math. Combin. Comput., 48 (2004) 157-177.
[7] Khurran H. Shafique, “Partitioning a Graph in Alliances and its Application to Data Clustering”, PhD Thesis, School of Computer Science, University of Central Florida, Orlando,
2004.
[8] José M. Sigarreta, “Alianzas en Grafos”, Tesis Doctoral, Departamente de Matemáticas,
Universidad Carlos III de Madrid, 2007.
[9] J. M. Sigarreta e J. A. Rodrı́guez-Velázquez, On Defensive Alliances and Line Graphs,
Applied Mathematics Letters, 19 (2006) 1345-1350.
[10] J. A. Rodrı́guez-Velázquez, I. G. Yero e J. M. Sigarreta, Defensive k-alliances in Graphs,
Applied Mathematics Letters, 22 (2009) 96-100.
679