Security, (F,I)-security, and Ultra-security in Graphs
by
Caleb Petrie
A dissertation submitted to the Graduate Faculty of
Auburn University
in partial ful llment of the
requirements for the Degree of
Doctor of Philosophy
Auburn, Alabama
August 4, 2012
Keywords: Graphs, Security, Hall?s Theorem
Copyright 2012 by Caleb Petrie
Approved by
Peter Johnson, Chair, Professor of Mathematics & Statistics
Dean Ho man, Professor of Mathematics & Statistics
Chris Rodger, Professor of Mathematics & Statistics
Abstract
Let G = (V;E) be a graph and S  V. The notion of security in graphs was  rst
presented by Brigham et al [3]. A set S is secure if every attack on S is defendable. The
cardinality of a smallest secure set of G is the security number of G.
We give several new de nitions of security. We show that some of these new de nitions
are equivalent to the de nition given by Brigham et al, while others are not. In these
new situations, we  nd necessary and su cient conditions for security. Various Hall-type
theorems are used in these proofs. We also de ne analogues of the security number and  nd
them for various classes of graphs.
ii
Acknowledgments
I would like to thank my advisor, Dr. Peter Johnson, for his work with me on this
research. I also want to thank Dr. Ed Thurber and Dr. Walt Stangl of Biola University,
for encouraging me to pursue graduate studies. Lastly, I would like to thank my parents,
David and Janette Petrie, for their support of my education from the day it began. Soli Deo
Gloria.
iii
Table of Contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Integer and Fractional Security . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.1 De nitons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 A New Proof of Theorem BDH . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 The Equivalence of (I,I)-security, (I,F)-security, and (F,F)-security . . . . . . 4
3 (F,I)-security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.1 Bipartite Graph Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.1.1 A Proof Using the Max-Flow Min Cut Theorem . . . . . . . . . . . . 8
3.1.2 A Proof by Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Main Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3 (F,I)-security Numbers of Various Graphs . . . . . . . . . . . . . . . . . . . 15
3.3.1 Complete Multipartite Graphs . . . . . . . . . . . . . . . . . . . . . . 19
4 Ultra-security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.1 A Necessary and Su cient Condition . . . . . . . . . . . . . . . . . . . . . . 22
4.2 The Ultra-security Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5 Relationships Between Security, (F,I)-security, and Ultra-security . . . . . . . . 29
5.1 Ultra-security Implies (F,I)-security . . . . . . . . . . . . . . . . . . . . . . . 29
5.2 Relating Security, (F,I)-security, and Ultra-security . . . . . . . . . . . . . . 31
5.2.1 An In nite Family of Graphs . . . . . . . . . . . . . . . . . . . . . . 32
iv
6 On the Security Number of Regular Bipartite Graphs . . . . . . . . . . . . . . . 34
6.1 d-regular Bipartite Graphs with s(G) = d . . . . . . . . . . . . . . . . . . . . 34
6.2 On the Security Number of Qn . . . . . . . . . . . . . . . . . . . . . . . . . 40
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
A An Alternative Proof that (I,I)-security Implies (F,F)-security . . . . . . . . . . 44
B A Table of Security Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
v
List of Figures
3.1 The network formed from the bipartite graph G. . . . . . . . . . . . . . . . . . 10
3.2 The set S =fs1;s2;s3g is not (F,I)-secure. . . . . . . . . . . . . . . . . . . . . . 17
5.1 A graph G such that s(G) = s(F,I)(G) <su(G): . . . . . . . . . . . . . . . . . . 32
5.2 A graph such that s(G) = s(F,I)(G) = su(G) = 3: . . . . . . . . . . . . . . . . . 33
6.1 S = A[B is secure in a 4-regular, bipartite graph. . . . . . . . . . . . . . . . . 36
vi
List of Tables
B.1 Security Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
vii
Chapter 1
Introduction
All graphs in this paper are  nite and simple. For a graph G = (V;E) and v2V we
will follow convention by letting N(v) =fujuv2Eg, and N[v] =fvg[N(v). For S V,
N(S) = [v2SN(v) and N[S] = N(S)[S. If not clear by the context, the graph G may
be indicated by the subscript: NG. The foundation for the study of security in graphs was
laid by Brigham, Dutton, and Hedetniemi in 2007 [3]. Security is a variation of the topic
of alliances in graphs, which is a just a few years older [13]. Given a graph G = (V;E),
they de ne an attack on S = fs1;s2;:::;skg V to be a collection of pairwise disjoint sets
A =fA1;A2;:::;Akg for which Ai N[si] S, 1 i k. A defense of S is a collection of
pairwise disjoint sets D =fD1;D2;:::;Dkg such that Di N[si]\S, 1 i k: An attack
is defendable if there is a defense D such that jDij jAij for 1  i k. In this setting,
each vertex in N[S] S can attack only one of its neighbors in S, and each vertex in S can
defend itself or one of its neighbors in S. The set S is de ned to be secure if for every attack
A on S there exists a defense of D of S such that jDij jAij for 1 i k. Brigham et al
show that a set S is secure if and only if for every X S, jN[X]\Sj jN[X] Sj. They
also de ne the security number of G, denoted s(G), to be the cardinality of a smallest secure
set in G. Some results and unsolved questions about the security number can be found in
[3, 4, 6, 12]. In the subsequent chapters we explore varying de nitions of security, and their
relationship to the original de nition, and to each other.
1
Chapter 2
Integer and Fractional Security
We consider the cases in which a vertex may send out attack or defense to as many
appropriate vertices as it wants, so long as the total amount of attack or defense from that
vertex sums to at most one. This chapter is joint work with Dr. Garth Isaak and Dr. Peter
Johnson and appears in [10].
2.1 De nitons
LetG = (V;E) be a graph andS V. An attack onS is a functionA:(V S) S![0;1]
such that A(u;v) = 0 if uv =2E and for u2V  S;Pv2N(u)\SA(u;v)  1: A defense of
S is a function D:S S ! [0;1] such that D(u;v) = 0 if u 6= v and uv =2 E and for
u2S;Pv2N[u]\SD(u;v)  1. Suppose that A is an attack on S and D is a defense of S.
For u2S let D (u) = Pv2N[u]\SD(v;u) and A (u) = Pv2N(u) SA(v;u). An attack A is
defendable if there exists a defense D such that for each u2S, D (u) A (u). The set S
is secure if every attack on S is defendable.
The de nition of attack and defense given by Brigham, et al in [3] corresponds to the
case A(u;v)2f0;1gfor all u2(V S);v2S and D(u;v)2f0;1gfor all u;v2S. We will
refer to these as integer attack and integer defense respectively. This naturally leads to four
scenarios:
a) an integer attack against an integer defense, (I,I);
b) an integer attack against a defense, (I,F);
c) an attack against an integer defense, (F,I);
d) an attack against a defense, (F,F).
2
(The letter F has been chosen to suggest the word \fractional".) For each situation there
is a corresponding de nition of security. For instance, a set S is (I,F)-secure if every integer
attack is defendable. We now explore relationships among the di erent kinds of security.
2.2 A New Proof of Theorem BDH
Lemma. If S  V is secure in G in any of the four senses, then for each set X  S,
jN[X]\Sj jN[X] Sj.
Proof. Suppose that, for some X S, jN[X]\Sj<jN[X] Sj. Make an integer attack
A on S by letting each vertex in jN[X] Sj attack any of its neighbors in X with its whole
unit of attack. Let every other vertex in N[S] S attack one of its neighbors in S, or none;
it does not matter. Then for any defense D of S,
X
x2X
D (x) =
X
x2X
X
u2N[x]\S
D(u;x) =
X
u2N[X]\S
X
x2X
D(u;x)
 
X
u2N[X]\S
1 =jN[X]\Sj<jN[X] Sj
=
X
x2X
A (x):
Therefore, for any such D, there must be some x2X such that D (x) <A (x): Thus
A is not defendable, and so S is not secure.
Brigham et al [3] gave a necessary and su cient condition for a set to be (I,I)-secure.
We shall refer to this as the BDH Theorem. As an aside, we give a short proof of this result
using Hall?s Theorem:
Theorem HRHV ([8, 14, 9]). Suppose P1;:::;Pn are sets and k1;:::;kn are non-negative
integers. There exist pairwise disjoint sets D1;:::;Dn such that Di  Pi and jDij = ki for
3
1 i n if, and only if, for each J f1;:::;ng;j[j2JPjj  Pj2Jkj.
Theorem BDH. A set S V is (I,I)-secure if and only if jN[X]\Sj jN[X] Sj for all
X S.
Proof. The necessity of the condition follows from the Lemma. Let G = (V;E) be a graph.
Let S = fs1;s2;:::;sng V be a set such that jN[X]\Sj jN[X] Sj for all X  S.
Let A = fA1;:::;Ang be an integer attack on S, by the original de nition in [3]. De ne
Pi = N[si]\S for 1 i n. Thus Pi is the set of potential defenders of si. Let ki =jAijfor
1 i n; ki is the number of attackers of si. For any J f1;2;:::;ng, let XJ =fsj jj2Jg.
Then we have Pj2Jkj = Pj2JjAjj jN[XJ] Sj jN[XJ]\Sj=
  
 Sj2JPj
  
 . By Theorem
HRHV we can  nd Di Pi for 1 i n such that the Di are pairwise disjoint andjDij= ki.
Thus D =fD1;:::;Dng is an integer defense that thwarts the attack, and S is secure.
As remarked in [3], Theorem BDH shows that the problem of deciding whether or not
S  V is (I,I)-secure is in co-NP: S is not (I,I)-secure if and only if there is a certi cate
proving that it is not, a set X S such thatjN[X]\Sj<jN[X] Sj. Reportedly, Dutton
[5] has recently shown that the problem is co-NP-complete.
2.3 The Equivalence of (I,I)-security, (I,F)-security, and (F,F)-security
In order to prove the next result, we need the following analogue of Hall?s Theorem due
to Bollob as and Varopoulos [1].
Theorem BV. Suppose that (X; ) is an atomless measure space, M1;:::;Mn are subsets
of X of  nite measure, and r1;:::;rn are non-negative real numbers. There exist pairwise
disjoint sets C1;:::;Cn such that Ci Mi and  (Ci) = ri;1 i n, if, and only if, for each
4
J f1;:::;ng we have  (Sj2JMj) Pj2Jrj.
Theorem. Let G = (V;E) be a graph and S V. Then (a) S is (I,I)-secure , (b) S is
(I,F)-secure , (c) S is (F,F)-secure.
Proof. We will show (c))(b))(a))(c) . If S is (F,F)-secure then all attacks on S are
defendable, so all integer attacks on S are defendable. Thus S is (I,F)-secure. Now suppose
S is (I,F)-secure. By the Lemma, for any X S it must be that jN[X]\Sj jN[X] Sj:
Therefore, by the BDH Theorem, S is also (I,I)-secure.
Let S be (I,I)-secure. ThenjN[X]\Sj jN[X] Sjfor all X S. Let A:(N(S) S) 
S![0,1] be an attack on S. (We restrict the domain of the attackers to N(S) S because all
vertices in V N(S) will have no attack.) Recall that for v2S, A (v) = Pu2N(v) SA(u;v).
LetfI(v)jv2Sgbe an indexed family of pairwise disjoint unit intervals in the real numbers.
These are the defense reservoirs of the vertices of S. For v2S let M(v) = Sw2N[v]\SI(w).
This is the total defense available to v. So we have another indexed family fM(v)jv2Sg.
Let  denote the Lebesgue measure. To achieve a successful fractional defense against the
attack A, it su ces to  nd an indexed family fC(v)jv 2Sg of pairwise disjoint Lebesgue
measurable sets such that for all v2S, C(v) M(v) and  (C(v)) = A (v). If such a family
is found, de ne a defense D:S S![0,1] by D(w;v) =  (I(w)\C(v)).
Then for v 2S we would have
D (v) =
X
w2S
D(w;v)
=
X
w2S
 (I(w)\C(v))
=  (
[
w2S
(I(w)\C(v))) [the intervals I(w);w2S are pairwise disjoint]
  (M(v)\C(v)) =  (C(v)) = A (v):
5
Also for each w2S,
X
v2S
D(w;v) =
X
v2S
 (I(w)\C(v))
=  (
[
v2S
(I(w)\C(v))  (I(w)) = 1:
So D is a defense of S, and it defends against A.
Now we will show that jN[X]\Sj jN[X] Sj for all X S implies the existence of
such a family fC(v) jv2Sg. By Theorem BV, it is su cient to show that for all X S,
P
v2XA
 (v)  (S
v2XM(v)). Suppose X S. We have
 (
[
v2X
M(v)) =  (
[
v2X
(
[
w2N[v]\S
I(w)))
=  (
[
w2N[X]\S
I(w)) =
X
w2N[X]\S
 (I(w))
=
X
w2N[X]\S
1 =jN[X]\Sj jN[X] Sj
 
X
u2N[X] S
X
v2S
A(u;v) 
X
u2N[X] S
X
v2X
A(u;v)
=
X
v2X
X
u2N[X] S
A(u;v) =
X
v2X
A (v):
This leaves the question of how (F,I)-security relates to (I,I)-security. Clearly, (F,I)-
security implies (I,I)-security, but we will show the converse does not hold.
Example. In [3] it is seen that any n2 vertices of Kn form an (I,I)-secure set; however, n 1
vertices are needed to be (F,I)-secure. Let S = fs1;:::;skg V(Kn) such that k n 2.
Then jV(Kn) Sj 2. Let v1;v2 2 V(Kn) S. Let A(v1;si) = 1jSj for 1  i  k and
A(v2;s1) = 1 and A(v2;si) = 0 for 2  i k. A successful integer defense of this attack
requiresjSj+ 1 defenders, so S is not (F,I)-defendable. So, in order for S to be (F,I)-secure,
6
jSj n 1. Any set S such that jSj= n 1 is (F,I)-secure.
So an (F,I)-secure set has a greater security than a set that is only (I,I)-secure. We
give a necessary and su cient condition, in the spirit of Theorem BDH, for (F,I)-security
in Chapter 3. It may be possible to obtain results similar to Theorem BDH and the main
theorem of this chapter when attack and defense capabilities are extended to general values,
and are not necessarily constant from vertex to vertex.
7
Chapter 3
(F,I)-security
Let G = (V;E) be a graph. We now give a necessary and su cient condition for a set
S  V to be (F,I)-secure. The (F,I)-security number of G, s(F,I)(G), is the cardinality of
a smallest (F,I)-secure set. The values of the (F,I)-security number for various classes of
graphs is determined.
3.1 Bipartite Graph Lemma
We develop a lemma about bipartite graphs for use in the proof of the Main Theorem.
This lemma is also used in determing the (F,I)-security number of various families of graphs,
including complete multipartite graphs. In the setting of (F,I)-security, the vertices that
are attacking can fractionalize, but defending vertices cannot. Thus, in order for S to be
(F,I)-secure, for any attack A there must be an integer defense D such that D (s) dA (s)e
for all s2S. In this case, we may as well suppose that every s2S contributes 1 to the sum
P
s2SD
 (s), and so we havejSj= P
s2SD
 (s) P
s2SdA
 (s)e. Given an attack A on a set
S in an (F,I)-security setting, the total e ective attack is Ps2SdA (s)e.
Bipartite Graph Lemma. Let G be a connected bipartite graph with bipartition (X;Y).
Among (F,I)-attacks on Y, the maximum total e ective attack possible is jXj+jYj 1.
3.1.1 A Proof Using the Max-Flow Min Cut Theorem
Lemma 1. Let G be a complete bipartite graph with bipartition (X;Y). Among (F,I)-
attacks on Y, the maximum total e ective attack possible is jXj+jYj 1.
8
Proof. Let X = fx1;:::;xmg and Y = fy1;:::;yng. Then we are looking for the largest
possible value of Pn1daiewhere a1;:::;an are non-negative real numbers that sum to m. We
have
daie<ai + 1; i = 1;:::;n
)
nX
1
daie<
nX
1
(ai + 1) = m+n
)
nX
1
daie m+n 1:
To achieve the bound in this inequality, let A(x1;yj) = 1n for 1 j n; and let A(xi;y1) = 1
for 2 i m.
Corollary 1. Let G be a bipartite graph with bipartition (X;Y). For any (F,I)-attack on
Y, the total e ective attack is less than or equal to jXj+jYj 1.
The proof of Lemma 1 gives a solution to a problem proposed in [11]. Next we use the
Max-Flow Min-Cut Theorem to show that this upper bound can be achieved when G is a tree.
Lemma 2. Let G = (V;E) be a tree with bipartition (X;Y). De ne f:V ! [0;1) by
f(v) = 1 for v 2 X and f(v) = dG(v) jYj 1jYj for v 2 Y. Then there exists a function
wt:E![0;1) such that for all v2V,
f(v) =
X
e2Ee incident to v
wt(e):
Proof. Create a digraph D from G by directing every edge from X to Y. Add a vertex s
and for each x2X, form an arc directed from s to x. Similarly, add a vertex t and for each
y2Y, form an arc directed from y to t. Let A[s;X] be the set of arcs with one end at s
9
and one end in X, A[Y;t] be the set of arcs with one end in Y and one at t, and A[X;Y]
denote the arcs with one end in X and one end in Y. From this digraph, form a network by
designating s the source and t the sink (see Figure 3.1). De ne the capacity function c as
follows: c(a) = 1 if a2A[s;X], c(a) = dG(y) jYj 1jYj if a2A[Y;t], and c(a) =1otherwise.
Note that Pa2A[Y;t] c(a) =jXj, because G is a tree.
s t
X Y
A[s,X] A[X,Y] A[Y,t]
Figure 3.1: The network formed from the bipartite graph G.
If we can  nd a  ow in this network of valuejXj, then the desired function wt on E(G)
can be found by assigning wt(e);e2E(G), to be equal to the  ow of the corresponding arc.
To show we can  nd a  ow of value jXj, we will show that the minimum cut has capacity
jXj. The capacity of a minimum cut is clearly less than or equal to jXj, because we can
form a cut by taking all the arcs of A[s;X] (or all the arcs of A[Y;t]). Now we will show
that every other cut has a capacity bigger than jXj.
Any cut including an arc of A[X;Y] will have in nite capacity. The only other cuts to
check must include some, but not all, arcs of A[s;X] and some, but not all, arcs of A[Y;t].
Let K be a cut that has at least one arc of A[s;X] and at least one arc of A[Y;t]. Let
X0 = fxjx2X and (s;x) =2Kg and Y0 = fyjy2Y and (y;t) =2Kg. By assumption about
K, jX0j 1 and jY0j 1. Note that there are no arcs between X0 and Y0; otherwise K
would not be a cut. The capacity of the cut K is jX X0j+Py2Y Y0
 
dG(y) jYj 1jYj
 
:
10
Since each edge of G has one end in X and one end in Y,Py2Y Y0 dG(y) is the number of
edges of G with one end in Y Y0. G hasjXj+jYj 1 edges. Each edge has an end in Y Y0 or
in Y0. An edge with an end in Y0 must have its other end in X X0, as noted above. Looking
at the forest induced in G by (X X0)[Y0, the most edges it can have isjX X0j+jY0j 1.
Thus, Py2Y Y0 dG(y) (jXj+jYj 1) (jX X0j+jY0j 1) =jXj jX X0j+jY Y0j.
So we have
c(K) =jX X0j+
X
y2Y Y0
 
dG(y) jYj 1jYj
 
 jX X0j+jXj jX X0j+jY  Y0j jYj 1jYj jY  Y0j
=jXj+jY  Y0j jY  Y0j+ jY  Y0jjYj
=jXj+ jY  Y0jjYj
>jXj:
Let G = (V;E) be a connected bipartite graph with bipartition (X;Y). By Corollary 1,
jXj+jYj 1 is an upper bound for the total e ective attack on Y. Also, G has a spanning
tree, and thus can achieve the bound ofjXj+jYj 1 by Lemma 2. One attack that achieves
this bound corresponds naturally to the function wt.
3.1.2 A Proof by Induction
Here we prove a more general result that implies the Bipartite Graph Lemma. Let
f:V ![0;1). A function wt:E![0;1) represents f if for all v2V,
f(v) =
X
e2Ee incident to v
wt(e):
11
Lemma 3. Let G = (V;E) be a tree and f:V ![0;1). Let (X;Y) be a bipartition of G.
If for all S such that S  X or S  Y, f(S) =
X
s2S
f(v)  f(NG(S)), then there exists a
function wt:E![0;1) that represents f.
Proof. Let (*) be the condition that for all S such that S X or S Y, f(S) =
X
s2S
f(v) 
f(NG(S)), and assume (*) holds. We will proceed by induction on jXj+jYj 2. First let
jXj + jYj = 2. Then V = fu;vg and E = fuvg. f(v)  f(u) and f(u)  f(v), so
f(v) = f(u). De ne wt(uv) = f(u). Now suppose that jXj+jYj> 2. Let u be a leaf in
G. Without loss of generality, u2X. Let v be the neighbor of u. By (*), f(u)  f(v).
De ne ef on G u by ef(v) = f(v) f(u) and ef(w) = f(w) for all other w 2V(G u).
We will show that the tree G u and the function ef satisfy (*). If S  X u and
v =2NG(S) = NG u(S), then ef(S) = f(S)  f(NG(S)) = ef(NG u(S)). If v2NG(S), then
ef(S) + f(u) = f(S[fug)  f(NG(S[fug)) = f(NG u(S)) = ef(NG u(S)) + f(u). So we
get that ef(S) ef(NG u(S)).
Now suppose S Y. If v =2S, then ef(S) = f(S) f(NG(S)) = ef(NG u(S)). If v2S
then ef(S) = f(S) f(u)  f(NG(S)) f(u) = f(NG u(S)) = ef(NG u(S)). So G u
with ef satis es (*). So there is a fwt : E(G u) ! [0;1) representing ef by the induction
hypothesis. Extend fwt to E(G) by putting weight f(u) on the edge uv. Call this extension
wt. It is straight forward to see that wt represents f.
Lemma 4. If G is a tree with bipartition (X;Y) then there exists an attack on Y by X with
a total e ective attack of jXj+jYj 1.
Proof. De ne f(v) = 1 for v2X and f(v) = dG(v) y 1y for v2Y where jYj = y. We
will show f can be represented by a function wt by applying Lemma 2. First suppose that
S Y. For any graph H let c(H) denote the number of connected components of H. Let
12
H(S) be the subgraph of G induced by S[NG(S). Note that H(S) is a forest. Then
f(S) =
 X
v2S
dG(v)
!
 y 1y jSj
=jE(H(S))j y 1y jSj
=jV(H(S))j c(H(S)) y 1y jSj
=jSj+jNG(S)j c(H(S)) y 1y jSj
=jNG(S))j+ 1yjSj c(H(S))
 jNG(S))j+ 1 c(H(S))
 jNG(S)j
= f(NG(S)):
Now suppose that S X. We want to show the following inequality:
f(S) =jSj
 f(NG(S)
=
0
@ X
v2NG(S)
dG(v)
1
A y 1y jNG(S)j
=jE(H(NG(S)))j y 1y jNG(S)j
=jNG(S)j+jNG(NG(S))j c(H(NG(S))) y 1y jNG(S)j
=jNG(NG(S))j+ 1yjNG(S)j c(H(NG(S))):
If NG(S) = Y, then c(H(NG(S))) = 1 and 1yjNG(S)j = 1yjYj = 1. So we need jSj 
jNG(NG(S))j. This holds because S NG(NG(S)).
Otherwise, jNG(S)j<jYjso NG(S) (Y. It su ces to show thatjSj+c(H(NG(S))) 
jNG(NG(S))j. Let u 2 Y such that u =2 NG(S). We will see that every component of
13
H(NG(S)) contains a vertex in NG(NG(S)) S that is not in any other component. If a
component C of H(NG(S)) did not have any vertices in NG(NG(S)) S, then it would not
be connected in G to u, a contradiction. So C must have a vertex in NG(NG(S)) S, and
it is not in any other component because components do not share vertices. So we have
jSj+c(H(NG(S))) jSj+jNG(NG(S)) Sj=jNG(NG(S))j:
So we can  nd a function wt to represent f. De ne an attack A by A(u;v) = wt(uv)
for every u2X and v2Y. The total e ective attack is then
X
v2Y
df(v)e=
X
v2Y
 
dG(v) y 1y
 
=
X
v2Y
dG(v) =jE(G)j=jXj+jYj 1:
The Bipartite Graph Lemma follows from Lemma 1 and Lemma 4.
3.2 Main Theorem
Given a graph G = (V;E) and a set S V, the set of edges with one end in set V  S
and one end in S induces a graph whose components are connected bipartite graphs. By
looking at the total e ective attack possible from the attackers in each component, we can
develop a necessary and su cient condition for (F,I)-security.
Let G = (V;E) be a graph and S =fs1;s2;:::;skg V. For X S, let GX denote the
subgraph of G whose vertex set is X[(N[X] S) and whose edge set is E[X;N[X] S],
the set of edges of G with one end in X and the other in N[X] S. Let C1;C2;:::;Ct be the
components of GX. Let Xi = V(Ci)\X for 1 i t.
Each Ci is a connected bipartite graph with bipartition (Xi;NG[Xi]  S). So the
maximum total e ective attack from NG[Xi] S to Xi is jXij+jNG[Xi] Sj 1. Since
Xi, 1  i t, are pairwise disjoint, the most attack that can be sent from V  S to X is
Pt
1(jXij+jNG[Xi] Sj 1) =jXj+jNG[X] Sj c(G
X), where c(GX) denotes the number
of components of GX.
14
In order for S to be (F,I)-secure, it is thus necessary that for all X S,jNG[X]\Sj 
jXj+jNG[X] Sj c(GX). The Main Theorem states that this condition is also su cient:
Main Theorem. Let G = (V;E) be a graph and S V. Then S is (F,I)-secure if, and
only if, jNG[X]\Sj jXj+jNG(X) Sj c(GX) for all X S.
The use of Theorem HRHV to prove the su ciency of this condition is similar to the
use of Theorem HRHV in Chapter 2.2 and Chapter 4.1.
Theorem HRHV ([8, 14, 9]). Suppose P1;:::;Pn are sets and k1;:::;kn are non-negative
integers. There exist pairwise disjoint sets D1;:::;Dn such that Di  Pi and jDij = ki for
1 i n if, and only if, for each J f1;:::;ng;j[j2JPjj  Pj2Jkj.
Proof of Main Theorem. Necessity has already been proven. Let G = (V;E) be a graph
and let S =fs1;s2;:::;sng V be such that for all X S, jNG[X]\Sj jXj+jNG(X) 
Sj c(GX). Let A be any attack on S, and Pi = N[si]\S for 1 i n. Let ki =dA (si)efor
1 i k. Then Pi is the set of potential defenders of si, and ki is the number of defenders
of si needed for a successful defense of A. For any J f1;:::;nglet XJ =[j2Jfsjg. Then we
havePj2Jkj jXJj+jNG(XJ) Sj c(GXJ) jNG[XJ]\Sj=j[j2J(NG[sj]\S)j=j[j2JPjj.
By Theorem HRHV we can  nd pairwise disjoint Di  Pi, 1  i n, such that jDij = ki
for 1 i n. Then D =fD1;:::;Dng is a succesful defense of A.
3.3 (F,I)-security Numbers of Various Graphs
Recall that for any graph G, s(G)  s(F,I)(G). Given two graphs G and H, we denote
their cartesian product by G H and their join by G_H. The path on n vertices is denoted
by Pn. Let Fn = K1_Pn and Wn = K1_Cn. As observed in [3], it is clear that a minimum
secure set is connected; that is, a minimum secure set induces a connected subgraph of the
15
graph in which it is a minimum secure set. Likewise, a minimum (F,I)-secure set is connected.
Proposition. Let G = (V;E) be a graph.
1) s(F,I)(G) = 1 if and only if  (G) 1 .
2)s(F,I)(G) = 2 if and only if  (G) = 2 and there exists uv2E such that d(u) = d(v) = 2.
3) s(F,I)(Pn Pm) = minfm;n;4g.
4) minfm;2n;6g s(F,I)(Cm Pn) minfm;2n;8g.
5) s(F,I)(Fn) = 1 + n2 , n 2.
6) s(F,I)(Wn) = 1 + n+12  , n 3.
Proof. 1) A vertex of degree zero or one is (F,I)-secure, but any vertex of greater degree is
not.
2) By the  rst result,  (G) > 1 is necessary for s(F,I)(G) = 2. Let S =fu;vgbe (F,I)-secure.
Since a minimum (F,I)-secure set is connected, uv2E. In order to be (F,I)-secure, S must
also be secure. So jN[S] Sj 2, which forces d(u)  3 and d(v)  3. If d(u) = 3 or
d(v) = 3, then c(GS) = 1, jN[S] Sj = 2, and jSj+jN[S] Sj c(GS) = 3 >jSj. So by
the Main Theorem, S is not (F,I)-secure. Thus d(u) = d(v) = 2 is necessary. If S =fu;vg,
uv2E, and d(u) = d(v) = 2, then the defense where u defends itself and v defends itself is
successful against any attack.
3) In [3] it is shown that s(Pn Pm) = minfm;n;3g. For the  rst case, suppose minfm;ng 
3. Then s(F,I)(Pn Pm) s(Pn Pm) = minfm;n;3g= minfm;ng. The n vertices that make
up the end vertices of the Pm paths form an (F,I)-secure set, and the m vertices that make
up the end vertices of the Pn paths form an (F,I)-secure set. So s(F,I)(Pn Pm) = minfm;ng.
Now suppose that minfm;ng 4. Then s(F,I)(Pn Pm)  s(Pn Pm) = minfm;n;3g = 3.
If S consists of a corner and its two neighbors, let S = fs1;s2;s3g, N[S] S = fv1;v2;v3g
16
and fs1s2;s1v1;s1v2;s3s2;s3v2;s3v3g be a subset of the edges (see Figure 3.2). Then the
attack A de ned by A(v1;s1) = 1;A(v2;s1) = 0:5;A(v2;s3) = 0:5, and A(v3;s3) = 1 is not
defendable. Any other S such thatjSj= 3 satis esjSj<jN[S] Sjand is not secure, much
less (F,I)-secure. Four vertices that induce a 4-cycle and include a corner vertex forms an
(F,I)-secure set. So in this case, s(F,I)(Pn Pm) = 4.
s1
s2 s3 v3
v1
v2
Figure 3.2: The set S =fs1;s2;s3g is not (F,I)-secure.
4) Kozawa et al [12] show that s(Cm Pn) = minfm;2n;6g. This settled a conjecture of
Brigham et al [3]. This gives the lower bound for the (F,I)-security number. Two consecu-
tive copies of Pn form an (F,I)-secure set, as does an m-cycle consisting of end vertices of
the paths. If m 4 and n 2, taking the end vertex of a path and its neighbor in the path,
in four consecutive paths, gives an (F,I)-secure set of eight vertices.
5) Suppose S is a minimum (F,I)-secure set and that V(K1) =2 S. The subgraph GS is
connected. By the Main Theorem, it is then necessary that 1 = c(GS)  jN(S) Sj. So
S = V(Pn) and jSj = n. If V(K1)  S, let S0 = V(Pn)\S; then jS0j n 1 (otherwise
S0 = V(Pn) and S = V(Fn)). Every vertex in V(Pn) S0 can attack V(K1) and there is
at least one u2V(Pn) S0 such that u has a neighbor in S0. De ne an attack by letting
u send a half unit of attack to V(K1) and a half unit of attack to its neighbor in S0. Let
17
every other vertex of V(Pn) S0 attack V(K1) with its whole unit of attack. To be defended
successfully, this attack requiresjSj= 1+jS0j jV(Pn) S0j+1 = n jS0j+1. This implies
that jS0j  n2 and thus jSj 1 + n2 . Next we construct an (F,I)-secure set S, such that
jSj= 1 + n2 . Let S be the set containing V(K1) and the  rst  n2 vertices of V(Pn). Only
two vertices can be attacked: V(K1) and some s2V(Pn)\S. Let s defend itself, and have
all other vertices of S defend the V(K1). Since s has exactly one neighbor in V(Pn) S, it
has su cient defense. Likewise, V(K1) has a total defense of  n2 , and the attack there is at
most  n2 : This defense is successful against any attack on S.
6) The proof is similar to the proof of 5). If a set S V does not include the V(K1), then
V(K1) can attack every vertex in the set S. In order for S to be (F,I)-secure, it can have no
other attackers. So S = V(Cn) andjSj= n. If an (F,I)-secure set S V includes V(K1), let
S0 = S\V(Cn). IfjS0j n 1, thenjSj n, and we already can  nd an (F,I)-secure set of
size n. If jS0j 1, then jSj 2 and S is not (F,I)-secure by inspection. (In fact, for n 4,
S is not secure.) So let 2  jS0j n 2. The graph GS is a connected bipartite graph.
Since every vertex in V(Cn) S0 is adjacent to V(K1), one part of the bipartition has size
jV(Cn) S0j= n jS0j. The other part of the bipartition must have at least three vertices,
because it is V(K1)[S0. By the Bipartite Graph Lemma, in order for S to be (F,I)-secure,
it is required that jSj = 1 +jS0j n jS0j+ 3 1. Isolating jS0j yields jS0j  n+12  . So
jSj 1 + n+12  .
An (F,I)-secure set of size 1+ n+12  can be found by taking V(K1) and n+12  consecutive
vertices of the V(Cn). Exactly three vertices can be attacked, V(K1), and some u;v2S0;
u and v each have exactly one neighbor in V(Cn) S0. Let u and v defend themselves, and
have every other vertex of S defend V(K1). Then u and v clearly have su cient defense,
while V(K1) has a total defense of  n 12  and at most the attack at V(K1) is  n 12  . So this
defense is successful against any attack on S.
18
3.3.1 Complete Multipartite Graphs
Next we  nd the (F,I)-security number of complete multipartite graphs. We begin with
a corollary of the Bipartite Graph Lemma.
Corollary 2. Let G be a complete bipartite graph with bipartition (X;Y). If S = X[Y1,
where jY1j=
j
jYj
2
k
and Y1  Y, then S is (F,I)-secure.
Proof. Let A be an attack on S. Let XA = fxjx2X and A (x) > 0g: By applying the
Bipartite Graph Lemma to the subgraph induced by XA[(Y  S), the maximum total
e ective attack possible is then
jXAj+jY  Sj 1 =jXAj+
 jYj
2
 
 1:
Construct a defense D as follows. Let every vertex in XA defend itself. This leaves
l
jYj
2
m
 1
e ective attack remaining, but jY1j =
j
jYj
2
k
 
l
jYj
2
m
 1. Since G is complete, the vertices
ofY1 can send their units of defense wherever they are necessary to  nish constructingD.
We will employ Corollary 2 in the following proof of Theorem 1, below. By inspection
s(F,I)(K2;2) = 2.
Theorem 1. If 2 n1  n2 and n2 6= 2, then s(F,I)(Kn1;n2) = n1 + n22  .
Proof. Let the bipartition of G = Kn1;n2 be (X;Y) where jXj = n1 and jYj = n2, and
let S  X[Y be (F,I)-secure. First assume S\Y = ;. Then S  X, S[Y induces a
complete bipartite graph, and there exists an attack on S by Y with a total e ective attack
of jYj+jSj 1. Since jYj 2 the value of this total e ective attack is strictly greater than
jSj, contradicting the assumption that S is (F,I)-secure. Thus we conclude that S\Y 6=;.
19
By a similar argument it follows that S\X6= ;. An (F,I)-secure set S V(Kn1;n2) must
therefore contain vertices of both X and Y. So let S\X6=;, S\Y 6=;, and let x =jX\Sj
and y = jY \Sj, so that x + y = jSj. Also note that x 1 and y  1. There are four
possible scenarios:
1) x =jXj and y =jYj. In this case S is (F,I)-secure because S = V(Kn1;n2).
2) 1  x < jXj and 1  y < jYj. (X \S) [ (Y  S) induces a complete bipar-
tite graph, so there exists an attack from Y  S to X \S with total e ective attack
jY  Sj+jX\Sj 1 = n2  y + x 1. Likewise, (Y \S)[(X S) induces a com-
plete bipartite graph, so there exists an attack from X S to Y \S with total e ective
attack jX Sj+jY \Sj 1 = n1 x + y 1. Since these two complete bipartite graphs
are disjoint, there exists an attack from V(Kn1;n2)  S to S with total e ective attack
(n2 y+x 1)+(n1 x+y 1) = n1+n2 2. SojSj n1+n2 2. Taking x =jXj 1 = n1 1
and y =jYj 1 = n2 1 provides an (F,I)-secure set of this size. The integer defense where
each vertex of S defends itself is successful against any attack.
3) x =jXjand 1 y<jYj. Only vertices in X can be attacked. There is a complete bipar-
tite graph induced by X[(Y S). So there is an attack of X by Y S with total e ective
attackjXj+jY Sj 1 = x+n2 y 1 = n1 +n2 y 1. In order for S to be (F,I)-secure,
it is necessary that jSj = x + y = n1 + y n1 + n2 y 1. Thus y  n2 12  =  n22  . So
jSj= x + y n1 + n22  . On the other hand, any set S with all the vertices of X and  n22  
vertices of Y is (F,I)-secure, by Corollary 2.
4) 1 x<jXjand y =jYj. Simlar to case 3), the smallest (F,I)-secure set in this case is of
size n2 + n12  .
20
So the s(F,I)(Kn1;n2) = minfn1 + n2;n1 + n2 2;n1 + n22  ;n2 + n12  g. The minimum
is n1 + n22  unless n1 = n2 = 2. So if n2 6= 2, s(F,I)(Kn1;n2) = n1 + n22  .
Theorem 2. Let k  3 and 1  n1  n2  :::  nk. Then s(F,I)(Kn1;n2;:::;nk) =
n1 +n2 +:::+nk 1 + nk2  .
Proof: Let fX1;X2;:::;Xkg be the partition of Kn1;n2;:::;nk so that jXij= ni for 1 i k.
Let V = V(Kn1;n2;:::;nk) and ;6= S  V. If jfi : (V  S)\Xi 6= ;gj 2, then the graph
induced by the edges with one end in S and one end in V S induces a connected bipartite
graph with bipartition (S;V  S). So V  S can attack S with a total e ective attack of
jV  Sj+jSj 1 2 +jSj 1 =jSj+ 1. So S cannot be (F,I)-secure. Thus V  S =; or
jfi : (V  S)\Xi6=;gj= 1. If V  S =;, then S = V. This is not a smallest (F,I)-secure
set, because any set S with jSj=jVj 1 is (F,I)-secure.
So we must havejfi : (V S)\Xi6=;gj= 1. Let X be such that (V S)\X 6=;and
(V S)\Xj =;for all j6=  . Let x =jS\X j. ThenjV Sj=j(V S)\X j= n  x.
There are no edges between S\X and V  S because both are contained in X . So the
complete bipartite graph induced by the edges with one end in V  S and one end in S has
bipartition (S X ;V  S). There is an attack from V  S to S X with total e ective
attackjV  Sj+jS X j 1 = n  x+jSj x 1. In order for S to be (F,I)-secure, it is
necessary thatjSj n  2x 1+jSjfrom which it follows x  n  12  =  n 2  . We can  nd
an (F,I)-secure set of size Pj6= nj + n 2  by choosing any  n 2  vertices of X along with
[j6= Xj. This set S is (F,I)-secure by Corollary 2, because S is (F,I)-secure in the complete
bipartite graph induced by edges with one end in X and one end in V  X . The other
edges in the multipartite graph do not allow for any new attack possibilities. Therefore,
s(F,I)(Kn1;n2;:::;nk) = min
1 i k
(X
j6=i
nj +
jni
2
k)
=
k 1X
j=1
nj +
jnk
2
k
:
21
Chapter 4
Ultra-security
In this chapter, we will look only at integer attacks and integer defenses. Recall that an
integer attack and an integer defense are equivalent to the de nitions given by Brigham et al
[3] and mentioned in the Introduction. In this chapter, we will use the notation of Brigham et
al. That is, for a graph G = (V;E) and S =fs1;:::;skg V, an integer attack is a collection
of pairwise disjoint sets A =fA1;:::;Akgsuch that Ai N[si] S for 1 i k. An integer
defense is a collection of pairwise disjoint sets D = fD1;:::;Dkg such that Di  N[si]\S
for 1  i k; an integer defense D of S such that jDij jAij for 1  i k is a successful
integer defense of A.
For a graph G = (V;E), this chapter looks at a reversal of the usual situation. This
course of inquiry was suggested by Dr. Chris Rodger. Usually we ask: For each integer
attack on S, does their exist a successful integer defense of S? Now we will ask the following
question: Is there one integer defense that will successfully defend against any integer attack?
A set S V is ultra-secure if there exists an integer defense D of S, such that for any integer
attack A on S, D is a successful integer defense of A. Note that if S  V is ultra-secure,
then S is secure.
4.1 A Necessary and Su cient Condition
The following Hall-type theorem is used in the proof of the Theorem after it.
Theorem HRHV ([8, 14, 9]). Suppose P1;P2;:::;Pn are sets and k1;k2;:::;kn are non-
negative integers. There exist pairwise disjoint sets D1;:::;Dn such that Di Pi andjDij= ki
22
for 1 i n if, and only if, for each I f1;:::;ng, j[i2IPij Pi2Iki.
Theorem HRHV is used in [10] to give an alternative proof of the necessary and suf-
 cient condtion for security due to Brigham et al [3]. Its use in the proof of the following
Theorem is similar.
Theorem. A set S V is ultra-secure if and only if jN[X]\Sj Px2XjN[x] Sj for all
X S.
Proof. Let S =fs1;s2;:::;skgbe ultra-secure, and X S. Suppose that D =fD1;:::;Dkgis
a successful integer defense of every integer attack on S. Let I =fij1 i k and si2Xg.
For eachi2I there exists an integer attackAonS withjAij=jN[si] Sj. IfS is ultra-secure,
thenjDij jN[si] Sjfor all i2I. Since Di\Dj =;for i6= j and Di N[si]\S N[X]\S
for i2I, it is necessary thatjN[X]\Sj Pi2IjDij Pi2IjN[si] Sj= Px2XjN[x] Sj.
To show su ciency, let S =fs1;s2;:::;sng V such that for all X S, jN[X]\Sj 
P
x2XjN[x] Sj. Let ki = jN[si] Sj and Pi = N[si]\S, 1  i n. For 1  i n, ki
represents the number of vertices that can attack si, and Pi is the set of potential defenders
of si. For I  f1;2;:::ng, letting X = fsiji2Ig, we have Pi2Iki = Pi2IjN[si] Sj =
P
x2XjN[x] Sj jN[X]\Sj = j[i2IPij. By Theorem HRHV, for 1  i n, there exist
pairwise disjoint Di  Pi such that jDij = ki. For any integer attack A = fA1;A2;:::;Ang
on S, jAij ki for 1  i n. It follows that D = fD1;D2;:::;Dng is a successful integer
defense of any integer attack A on S.
4.2 The Ultra-security Number
The security number s(G) of a graph G is the cardinality of a smallest secure set in
G. Some results on the security number can be found in [3, 4, 6, 12]. Given a graph G,
23
the ultra-security number, denoted su(G), is the cardinality of a smallest ultra-secure set in
G. Note that for any graph G, s(G)  su(G). Comments by Dr. Amin Bahmanian led to
improvements in the statements of parts 1) and 2) in the following result.
Proposition. Let G = (V;E) be a graph.
1) su(G) = 1 if and only if  (G) 1.
2) su(G) = 2 if and only if  (G) = 2 and there exits uv2E such that d(u) = d(v) = 2.
3) su(Kn) = n 1, if n 2.
4) su(Pn Pm) = minfm;n;4g.
5) su(Km;n) = min
n
m+n 2;m+
l
m(n 1)
m+1
mo
;2 m n.
6)Let k 3 and 1 n1  ::: nk. Let n = Pki=1ni. Then su(Kn1;:::;nk) = n 
j
n
n nk+1
k
.
Proof. 1) A single vertex of degree zero or one is ultra-secure, but any vertex with degree
greater than one is not.
2) For su(G) > 1,  (G)  2 is required. Let S  V with jSj = 2. If S contains two
nonadjacent vertices, it is not ultra-secure. In order for a set S =fu;vg with uv2E to be
ultra-secure,jN[u] Sj+jN[v] Sj 2. Note thatjN[u] Sj 1 andjN[v] Sj 1, so that
jN[u] Sj= 1 andjN[v] Sj= 1 is required. Furthermore,jN(u)\Sj=jN(v)\Sj= 1 and
thus d(u) = d(v) = 2 is necessary. If S =fu;vg, uv2E, and d(u) = d(v) = 2, then the inte-
ger defense where u defends itself and v defends itself is successful against any integer attack.
3) Suppose that S V is ultra-secure and 1 jSj n 2. Then for x2S,jN[x] Sj 2.
It is necessary thatjN[S]\Sj Px2SjN[x] Sj, butjN[S]\Sj=jSjandPx2SjN[x] Sj 
P
x2S 2 = 2jSj. So S is not ultra-secure. Any S with jSj= n 1 is ultra-secure; D is found
by letting each vertex of S defend itself.
24
4) In [3] it is shown that s(Pn Pm) = minfm;n;3g. First suppose that minfm;ng 3.
Then we have su(Pn Pm) s(Pn Pm) = minfm;n;3g= minfm;ng. The m vertices of an
end column, and the n vertices of an end row are ultra-secure, so su(Pn Pm) minfm;ng,
and thus su(Pn Pm) = minfm;ng. Now suppose that minfm;ng 4. Then su(Pn Pm) 
s(Pn Pm) = minfm;n;3g= 3. Let S be a set consisting of a corner and its two neighbors.
Then Ps2SjN[s] Sj = 4, and jSj = 3. So three vertices of a corner do not form an
ultra-secure set. Any other set S with jSj= 3 satis es jSj<jN[X] Sj and is not secure,
much less ultra-secure. Four vertices that induce a C4 and contain a corner vertex form an
ultra-secure set. Thus when minfm;ng 4, su(Pn Pm) = 4. Combining the two cases we
get the desired result: su(Pn Pm) = minfm;n;4g.
5) Let (Y;Z) be the bipartition ofV(Km;n) such thatjYj= mandjZj= n. LetS V(Km;n).
For S to be ultra-secure, by the Theorem, it is necessary thatjSj Px2SjN[x] Sj. Clearly
jSj=jS\Yj+jS\Zj. On the other hand,
X
x2S
jN[x] Sj=
X
x2S\Y
jN[x] Sj+
X
x2S\Z
jN[x] Sj
=
X
x2S\Y
jZ Sj+
X
x2S\Z
jY  Sj
=jS\YjjZ Sj+jS\ZjjY  Sj:
So in order to be ultra-secure, S must satisfy the inequality:
jS\Yj+jS\Zj jS\YjjZ Sj+jS\ZjjY  Sj: (4.1)
If S Y, then jZ Sj = jZj 2, because 2  m n, and the inequality (4.1) fails.
Likewise, if S Z, the inequality (4.1) will fail. So for S to be ultra-secure, it is necessary
that S\Y 6=; and S\Z6=;. We will consider three cases.
25
First assume that Y  S6= ; and Z S6= ;. Inequality (4.1) implies 0  (jZ Sj 
1)jS\Yj+ (jY Sj 1)jS\Zj. SincejS\Yj 1 andjS\Zj 1, we havejZ Sj 1 and
jY Sj 1. So if there are attackers in both parts of the bipartition, there may be at most
one attacker from each part. LettingjS\Yj= m 1 andjS\Zj= n 1, S is ultra-secure
and jSj= m+n 2. The integer defense is given by letting each vertex of S defend itself.
For the second case, assume Y  S =; and Z S6=;. In this case, the inequality (1)
becomes jYj+jS\Zj jYjjZ Sj which is equivalent to m +jS\Zj m(n jS\Zj).
Isolating jS\Zj yields
jS\Zj 
 m(n 1)
m+ 1
 
:
Let S contain all m vertices of Y and
l
m(n 1)
m+1
m
vertices of Z. We will show this set satis es
the condition of the Theorem. For any v2Z\S, jN[v] Sj = 0, so we can assume that
X S\Y = Y. For X Y,
jN[X]\Sj=jXj+
 m(n 1)
m+ 1
 
and
X
x2X
jN[x] Sj=jXj
 
n 
 m(n 1)
m+ 1
  
:
So S is secure if and only if for all X Y,
jXj+
 m(n 1)
m+ 1
 
 jXj
 
n 
 m(n 1)
m+ 1
  
:
This inequality reduces to  
m(n 1)
m+ 1
 
 jXj(n 1)jXj+ 1 : (4.2)
Since m =jYj jXj it follows that
m
m+ 1  
jXj
jXj+ 1:
This shows that (2) holds and we have an ultra-secure set S with jSj= m+
l
m(n 1)
m+1
m
.
26
For the  nal case, assume Y  S6=; and Z S =;. Following a similar argument to
the second case, S must satisfy jSj n +
l
n(m 1)
n+1
m
. Since n m it follows that m 1n+1 < 1
and thus  
n
n+ 1(m 1)
 
=
 
(m 1) m 1n+ 1
 
= m 1:
So in this case, a minimum ultra-secure set S has jSj n+m 1.
Thus su(Km;n) = minfm+n 2;m+ mm+1(n 1) g. For 2 m n,
m+n 2 m+
 m
m+ 1(n 1)
 
, n 2 
 
(n 1) n 1m+ 1
 
, n 1m+ 1 < 2
, n 2m+ 2:
So we have, for 2 m n,
su(Km;n) =
8
><
>:
m+n 2 if n 2m+ 2
m+
l
m(n 1)
m+1
m
otherwise
as an alternative statement for su(Km;n). Comparing the two expressions in the reverse order
gives m+
l
m(n 1)
m+1
m
 m+n 2 if m+ 2 n. So we have m+n 2 = m+
l
m(n 1)
m+1
m
if and
only if m+ 2 n 2m+ 2.
6)Let X1;:::;Xk be the partition of Kn1;:::;nk, so that jXij = ni for 1  i  k. Let V =
V(Kn1;:::;nk) and let ;6= S V. If jfijXi\(V  S) 6= ;gj 2, then it is easy to see that
jN[x] Sj 1 for all x2S. Further, because k 3, it follows thatjN[y] Sj 2 for some
y2S. Then jSj<Px2SjN[x] Sj and S is not ultra-secure.
Now suppose that S is ultra-secure and jfijXi\(V  S)6=;gj= 0. Then S = V, but
this is not a minimum ultra-secure set, because any set of n 1 vertices is ultra-secure. So let
27
jfijXi\(V S)6=;gj= 1. Let  2f1;:::;ngsuch that X \(V S)6=;. Let r =jS\X j.
In order for S to be ultra-secure, we must have n n + r = jSj Px2SjN[x] Sj =
P
x2(S X )(n  r) = (n n )(n  r). Solving for r yields r  
l
n  nn n +1
m
. Thus
jSj = n n + r n n +
l
n  nn n +1
m
= n 
j
n
n n +1
k
. We will  nd an ultra-secure
set with minfn 
j
n
n ni+1
k
j1 i kg= n 
j
n
n nk+1
k
vertices.
Let S be the set consisting of the vertices V Xk and
l
nk nn n
k+1
m
of Xk. If nk  n2 ,
then n 
j
n
n nk+1
k
= n 1, and S is ultra-secure. If nk  n2 +1, then consider the complete
bipartite graph induced by the edges with one end in Xk and the other end in V Xk. One
part of the bipartition has size n nk, and the other part has size nk. In the proof of 5),
it was shown that a set consisting of all m vertices of the smaller part and
l
m(p 1)
m+1
m
of the
larger part forms an ultra-secure set. The set S does contain all n nk vertices of V  Xk,
and
l
nk nn n
k+1
m
=
l
(n nk)(nk 1)
n nk+1
m
vertices of Xk. So S is ultra-secure in the complete
bipartite graph. Thus S is also ultra-secure in the complete multipartite graph, because the
additional edges o er no new attack possiblities.
28
Chapter 5
Relationships Between Security, (F,I)-security, and Ultra-security
At this point, we have seen that for a graph G, s(G) s(F,I)(G) and s(G) su(G). In
this chapter, we explore further relationships between these three types of security.
5.1 Ultra-security Implies (F,I)-security
Let G = (V;E) be a  nite, simple graph. Let S  V. We compare (F,I)-security to
ultra-security. An equivalent formulation of ultra-security requires each vertex of N(S) S
to send one unit of attack along each edge it has into S. Note that in ultra-security the
attacks are integer attacks, and the defenses are integer defenses.
Lemma 1. Let G=(V,E) be a graph, and S V. Then S V is ultra-secure if and only
if there exists an integer defense D such that for all v2S, D (v) jN[v] Sj.
Proof. Suppose D is an integer defense such that for all v2S, D (v) jN[v] Sj. In any
attack A, A (v) jN[v] Sj and so for all v2V, A (v) jN[v] Sj D (v). Thus D is
successful against A and S is ultra-secure.
If S is ultra-secure, then there exists a defense D that is a successful defense of any
attack on S. For each v2S, there exists an attack such that A (v) =jN[v] Sj. Since D
is a successful defense of all attacks, D (v) jN[v] Sj.
Proposition 1. Let G = (V;E) be a graph and S  V. If S is ultra-secure, then S is
(F,I)-secure.
29
Proof. Let S V be an ultra-secure set, and A a (fractional) attack on S. Note that for
u2N(S) S and v2S, A(u;v) 1. So then A (v) = Pu2N[v] SA(u;v) Pu2N[v] S 1 =
jN[v] Sj. Due to Lemma 1, because S is ultra-secure, there is an integer defense D such
that for all v2S, D (v) jN[v] Sj A (v), and thus S is also (F;I)-secure.
Note that this shows s(F,I)(G)  su(G). In the proofs of the values of s(F,I)(Fn),
s(F,I)(Wn), and s(F,I)(Cm Pn) in Chapter 3.3, it is easy to see that the minimum (F,I)-
secure sets constructed are also ultra-secure.
Proposition 2.
1) su(Fn) = 1 + n2 ;n 2.
2) su(Wn) = 1 + n+12  , n 3.
3) minfm;2n;6g su(Cm Pn) minfm;2n;8g.
Now we look at one condition which will guarantee an (F,I)-secure set is also ultra-
secure. Recall that given a graph G = (V;E) and X  S  V, we de ne GX to be the
subgraph of G whose vertex set is X[(N[X] S) and whose edge set is the set of all edges
with one end in X and one end in N[X] S.
Proposition 3. If S V is (F,I)-secure and GS is a forest, then S is ultra-secure.
Proof. If GS is a forest, then for X S, GX is a forest because E(GX) E(GS). Since GX
is a forest jE(GX)j=jV(GX)j c(GX) =jXj+jNG[X] Sj c(GX). On the other hand,
recalling GX is bipartite with bipartition (X;NG[X] S), jE(GX)j = Px2XjNG[x] Sj.
Since S is (F,I)-secure, we have, for all X S,jNG[X]\Sj jXj+jNG[X] Sj c(GX) =
jE(GX)j= Px2XjNG[x] Sj. So S is also ultra-secure.
30
5.2 Relating Security, (F,I)-security, and Ultra-security
Let G = (V;E) be a graph. By Proposition 1, we now have s(G)  s(F,I)(G)  su(G).
Below are the necessary and su cient conditions for the three kinds of security:
S is secure,for all X S;jN[X]\Sj jN[X] Sj;
S is (F,I)-secure,for all X S;jN[X]\Sj jXj+jN[X] Sj c(GX);
S is ultra-secure,for all X S;jN[X]\Sj 
X
x2X
jN[x] Sj:
Note that for any X  S, jN[X] Sj Px2XjN[x] Sj. If S  V is secure and for all
X S,jN[X] Sj= Px2XjN[x] Sj, then S is also ultra-secure, and therefore (F,I)-secure.
Also note that jN[X] Sj = Px2XjN[x] Sj for all X  S if, and only if, for each pair
s1;s2 2S, s1 6= s2, N(s1)\N(s2) S =;; that is, any two vertices of S have no common
neighbor outside of S. So potential attackers do not have any choice as to where they can
send their attack.
Proposition 4. Let G = (V;E) be a graph and S V be secure. If for distinct s1;s2 2S,
N(s1)\N(s2) S =;, then S is (F,I)-secure and ultra-secure.
Corollary. Let G = (V;E) be a graph. If there exists a minimum secure set S  V such
that for distinct s1;s2 2S, N(s1)\N(s2) S =;, then s(G) = s(F,I)(G) = su(G).
However; there are in nitely many graphs where the condition in Proposition 4 fails
for every minimum secure set, and yet s(G) = s(F,I)(G) = su(G) still holds. The smallest
example is K3.
Because s(Kn) =  n2 , s(F,I)(Kn) = n 1, and su(Kn) = n 1, we see it is possible
to have a graph G where s(G) < s(F,I)(G) = su(G). Likewise, when n 5, s(Kn;n) = n,
s(F,I)(Kn;n) = n+ n2 , and su(Kn;n) = 2n 2, so Kn;n is an example of a graph G such that
31
s(G) <s(F,I)(G) <su(G).
Example. We will show the graph G in Figure 5.1 satis es s(G) = s(F,I)(G) = 3 and
su(G) = 4. There is no vertex of degree one, and no subset of size two is secure, so s(G) 3.
The subset fa;b;fg is a secure set. Applying the Main Theorem of Chapter 3 shows that
fa;b;fg is also (F,I)-secure. No subset of size three is ultra-secure: there are 14 subsets of
size three that induce a connected subgraph in G, and each fails the necessary and su cient
condition for ultra-security. The setfb;c;e;fgis ultra secure. The defense where each vertex
defends itself is a successful defense against any attack.
a
b c
d
ef
Figure 5.1: A graph G such that s(G) = s(F,I)(G) <su(G):
5.2.1 An In nite Family of Graphs
So far, we have seen examples of graphs G such that s(G) = s(F,I)(G) = su(G)2f1;2g.
Proposition 5. For each positive integer n, there exists a graph G such that s(G) =
s(F,I)(G) = su(G) = n.
Proof. Clearly s(Pn) = s(F,I)(Pn) = su(Pn) = 1 and s(Cn) = s(F,I)(Cn) = su(Cn) = 2. For
n = 3, the graph G = (V;E) in Figure 5.2 satis es s(G) = s(F,I)(G) = su(G) = 3. The set
32
S = fs1;s2;s3g is an ultra-secure set of order three, and no secure set of order one or two
exists.
s1 s2 s3
Figure 5.2: A graph such that s(G) = s(F,I)(G) = su(G) = 3:
For n  4, we generalize the graph in the  gure. Let G = (V;E) be such that
jVj= 3n+1. Let the vertices of the graph befs1;:::;sng[fv1;:::;v2n+1g: Let E =fsisi+1j1 
i n 1g[fvjvkjj 6= kg[fvisij1  i n 1g[fv1sng. Then fv1;:::;v2n+1g induces a
K2n+1 and fs1;:::;sng induces a Pn. Letting each si defend itself shows that fs1;:::;sng is
ultra-secure with size n. So we have s(G)  s(F,I)(G)  su(G)  n. We will now show
s(G) n, and the result follows. Let S V be secure. If vj2S for some j thenjSj n+1,
becausejN[vj]\Sj jN[vj] SjandjN[vj]j 2n+ 1. So we can  nd no smaller secure set
containing any vj. So if there is a smaller secure set, it has to be a subset of fs1;:::;sng. A
minimum secure set is connected [3], meaning the subgraph induced by the minimum secure
set is connected. So let T be a subset offs1;:::sngsuch thatjTj n 1, and T induces a con-
nected subgraph. Thenj(N[T] T)\fv1;:::;v2n+1gj=jTjandj(N[T] T)\fs1;:::;sngj 1,
so that jTj<jTj+ 1 jN[T] Tj, and T is not secure.
Note that in the proof above, the vertices of V  fs1;:::;sng do not have to induce a
K2n+1. If jVj> 3n + 1, so that jV  fs1;:::;sngj> 2n + 1, it is su cient for the vertices of
V  fs1;:::;sng to induce any graph H with  (H) 2n.
33
Chapter 6
On the Security Number of Regular Bipartite Graphs
6.1 d-regular Bipartite Graphs with s(G) = d
It has been shown that for a graph G, s(G)    +12  [6]. If G is d-regular, then
s(G)  d+12  . The complete graph Kn, achieves this bound, as it is regular of degree n 1
and s(Kn) =  n2 . When n 4,  n2 <n 1. So if G is a d-regular graph, it is possible that
s(G) < d. If we require G to be bipartite, in addition to being regular, then the security
number cannot be less than the degree.
Proposition 1. Suppose G=(V,E) is a regular bipartite graph with degree d. Then s(G) d.
Proof. If d = 0 or d = 1, s(G) = 1. Let d  2. Then s(G)  2 and a secure set S
must contain vertices u;v such that uv 2 E. The vertices u and v must be in di erent
parts of the bipartition, and thus jN[fu;vg]j = 2d. If S is secure, then by Theorem BDH
jN[fu;vg]j= 2d =jN[fu;vg] Sj+jN[fu;vg]\Sj 2jN[fu;vg]\Sj, sojN[fu;vg]\Sj d.
Thus we have jSj jN[fu;vg]\Sj d.
We now characterize the structure of d-regular, bipartite graphs with s(G) = d.
Theorem 1. Suppose G = (V;E) is a regular, bipartite graph with degree d  2 and
s(G) = d. Let S be a secure set with jSj = d. Then we can label the bipartition (Y;Z) in
such a way that S = A[B, A  Y, B  Z, jAj =  d2 , and jBj =  d2 . Furthermore,
for u;v2A, B  N(u) = N(v), and for w;z2B, A N(w) = N(z). Conversely, if G
has a bipartition (Y;Z) with A  Y and B  Z satisfying the preceding conditions, then
34
S = A[B is a secure set in G with jSj= d.
Proof. Name the bipartition (Y;Z) in such a way that jS\Yj jS\Zj. Let A = S\Y
and B = S\Z. Suppose jAj   d2 + 1. Then jBj   d2  1. Let u 2 A. Then
jN(u) Sj= d jN(u)\Bj d ( d2  1) =  d2 +1 > d2  jN[u]\Sj, which contradicts
S being secure. Therefore jAj  d2 . Since jAj jBj we must have jAj =  d2 , and thus
jBj =  d2 . Now d = jSj jN[S] Sj. For u2A, jN(u) Sj d jBj =  d2 . Likewise,
for w 2 B, jN(w) Sj d jAj =  d2 . Since (N(u) S)\(N(w) S) = ;, we have
jN[S] Sj jN(u) Sj+jN(w) Sj d. So we must have jN[S] Sj= d, which means
thatjN(u) Sj=  d2 ,jN(v) Sj=  d2 , N[S] S = (N(u)[N(w)) S, N(u)\S = B, and
N(w)\S = A. So for any v2A, v6= u, N(v) S N(u) S, and N(v)\S B. Since
N(u) = d and jN(u) Sj+jBj= d, we must have N(v) = N(u). Similarly, for any z2B,
z6= w, we have N(z) = N(w). Now suppose that G has a bipartition (Y;Z) with A Y
and B Z satisfying the preceding properties. By Theorem BDH, S = A[B is secure in
G if for all X S, jN[X]\Sj jN[X] Sj. We examine three cases. First, if ;6= X A,
then jN[X]\Sj=jXj+jBj=jXj+ d2   d2 =jN[A] Sj jN[X] Sj. If ;6= X B,
then jN[X]\Sj = jXj+jAj = jXj+  d2 >  d2 = jN[B] Sj jN[X] Sj. Lastly, if
X\A6=;and X\B6=;, thenjN[X]\Sj=jAj+jBj= d =jN[S] Sj jN[X] Sj. So
S = A[B is secure and jSj= d.
Figure 6.1, below, uses the notation of Theorem 1. In the case G is 4-regular and
bipartite, Figure 6.1 shows the subgraph of G induced by the set of edges with at least one
end in the secure set S = A[B.
For any regular, bipartite graph the number of vertices in one part of the bipartition
must equal the number of vertices in the other part. So the total number of vertices must
be even. The d-regular, bipartite graph with the fewest vertices is Kd;d, and s(Kd;d) = d.
35
A B
Figure 6.1: S = A[B is secure in a 4-regular, bipartite graph.
Lemma 1. There does not exist a d-regular, bipartite graph G = (V;E) such that s(G) = d
and 2d<jVj< 3d.
Proof. We proceed by contradiction. Suppose that G = (V;E) is a d-regular, bipartite
graph such that s(G) = d and 2d <jVj< 3d. We can label the bipartition (Y;Z) in such
a way that there is a secure set S = A[B as in Theorem 1. Letting A0 = N(B) A
and B0 = N(A) B, it follows that jA[A0j = jB[B0j = d. Since d <jZj there exists
v2Z (B[B0) such thatjN(v)j= d and N(v) Y A. SincejYj< 3d2 andjAj=  d2 , it
follows that jN(v)j jY  Aj< 3d2   d2  d, contradicting jN(v)j= d.
Lemma 2. If d > 0 is even, there exists a d-regular, bipartite graph G = (V;E) such that
s(G) = d and jVj= 3d. If d is odd, there exists a d-regular, bipartite graph G = (V;E) such
that s(G) = d and jVj= 3d+ 1.
Proof. First suppose that d is even. Let V be a set such thatjVj= 3d. Partition the V into
two sets, Y and Z such thatjYj=jZj= 3d2 . Partition vertices of Y into three sets A;A0;A00
such that jAj = jA0j = jA00j = d2. Partition the vertices of Z into three sets B;B0;B00 such
36
that jBj=jB0j=jB00j= d2. De ne the edge set
E =fuvju2A;v2B[B0g[fuvju2A0;v2B[B00g[fuvju2A00;v2B0[B00g:
Letting G = (V;E) and S = A[B, S satisifes the conditions of Theorem 1 and is secure in
G.
Now suppose that d is odd. Let V be a set such that jVj = 3d + 1. Partition the
V into two sets, Y and Z such that jYj = jZj = 3d+12 . Partition the vertices of Y into
three sets A;A0;A00 such that jAj = jA00j = d+12 and jA0j = d 12 . Partition the vertices of
Z into three sets B;B0;B00 such that jBj = d 12 and jB0j = jB00j = d+12 . Let r = d+12 ,
A00 = fa1;:::;arg and B0 = fb1;:::;brg. Let F = faibij1  i  rg. De ne the edge set
E = (fuvju2A;v2B[B0g[fuvju2A0;v2B[B00g[fuvju2A00;v2B0[B00g) F.
Letting G = (V;E) and S = A[B, S satis es the conditions of Theorem 1 and is secure in
G.
Theorem 2. There exists a d-regular, bipartite graph G = (V;E) such that s(G) = d, if and
only if jVj= 2d, or jVj 3d and jVj is even.
Proof. Let G = (V;E) be a d-regular, bipartite graph such that s(G) = d. The discussion
preceding Lemma 1 shows that jVj must be even and that Kd;d satis es s(G) = d and
jVj = 2d. So if G is not isomorphic to Kd;d, then, by Lemma 1, jVj 3d. We proceed by
induction, Lemma 2 providing the base when d is even or d is odd.
Let jVj 3d + 2 and jVj even. Let H = (U;F) be a d-regular, bipartite graph with
jUj = jVj 2 satisfying s(H) = d. As in Theorem 1, we can write the bipartition of H as
(Y;Z) and  nd a secure set S = A[B. Construct the graph G = (V;E) as follows. Add a
vertex u to Y and a vertex v to Z. We now  nd a set of d independent edges in H, using
Hall?s Theorem.
37
Case 1: d is even. Let Y0 = (V(H)  S) \Y and Z0 = (V(H)  S) \Z. Since
jUj=jVj 2 3d, we have jYj=jZj 3d2 so that jY0j=jZ0j=jYj d2  d. Also, Y0 has
d
2 vertices of degree
d
2 in H S, and every other vertex has degree d. Let D Y
0 such that
jDj= d. Examine the graph  induced by D[Z0. Let X D. If X has a vertex of degree
d, then jXj d N (X). If X does not have a vertex of degree d, then each vertex in X
has degree d2, and jXj d2  N (X). So by Hall?s Theorem, there must be a matching in  
that saturates D. Let M be this set of d independent edges, which are also independent in
H S and H.
Case 2: d is odd. Let Y0 = (V(H)  S) \Y and Z0 = (V(H)  S) \Z. Since
jUj = jVj 2  3d + 1, we have jYj = jZj  3d+12 , so that jY0j = jYj jY \Sj  
3d+1
2  
d+1
2 = d andjZ
0j=jZj jZ\Sj 3d+1
2  
d 1
2 = d+ 1. In H S, Y
0 has d 1
2 vertices
of degree d+12 , and every other vertex of Y0 has degree d. Let D Y0 such that jDj = d.
Examine the graph  induced by D[Z0. Let X D. If X has a vertex of degree d, then
jXj d N (X). If X does not have a vertex of degree d, then each vertex in X has degree
d+1
2 , and jXj 
d 1
2 <
d+1
2  N (X). So by Hall?s Theorem, there must be a matching in  
that saturates D. Let M be this set of d independent edges, which are also independent in
H S and H.
Next we decribe how to obtain the edge set E from F. For each w1w2 2M, w1 2Y S
and w2 2Z S, delete w1w2 from F, and replace it by two edges: w1v and w2u. Thus the
degree of every vertex of (Y  S)[(Z S) is not changed, and the degree of u and of v
is d. Then G = (V;E) is a d-regular, bipartite graph on jVj vertices. But the neighbors of
vertices in S in G are the same as in H, so S is secure in G = (V;E).
Proposition 2. Let G = (V;E) be a d-regular, bipartite graph such that s(G) = d. If
jVj2f2d;3d;3d+ 1g then the graph G is unique up to isomorphism.
38
Proof. Let S be a secure set in G = (V;E) of order d. By Theorem 1, we can lable the
bipartition of G (Y;Z) so that there is a secure set S = A[B where A and B have the
properties listed. Let A0 = N(B) A and B0 = N(A) B. Note that jA0j =  d2 and
jB0j=  d2 .
Suppose jVj= 2d. In this case, Y = A[A0, Z = B[B0, jYj= d, and jZj= d. Since
every vertex has degree d, the graph must be isomorphic to Kd;d.
Now suppose that jVj = 3d. In this case, d must be even. Let A00 = Y  (A[A0)
and B00 = Z (B[B0). Note that jAj = jA0j = jA00j = jBj = jB0j = jB00j = d2. Let
F =fuvju2A;v2B[B0g[fuvju2B;v2A0g. By Theorem 1, F  E. Note that every
vertex of A[B is incident with d edges of F. So no vertex in A is adjacent to a vertex in
B00, and no vertex in B is adjacent to a vertex in A00. In order for each vertex of A00 to have
degree d, it must be adjacent to every vertex in B0[B00. Likewise, every vertex of B00 must
be adjacent to every vertex of A0[A00. This forces E =fuvju2A;v2B[B0g[fuvju2
A0;v2B[B00g[fuvju2A00;v2B0[B00g:
Lastly, supposejVj= 3d+ 1. In this case, d must be odd. Again, let A00 = Y (A[A0)
and B00 = Z (B[B0). Note thatjAj=jA00j=jB0j=jB00j= d+12 andjBj=jA0j= d 12 . Let
F1 =fuvju2A;v2B[B0g[fuvju2B;v2A0g. By Theorem 1, F1  E. Every vertex
of A[B is incident with d edges in F1. So no vertex of B00 is adjacent to any vertex of A.
Likewise, no vertex of A00 is adjacent to any vertex of B. In order to have degree d, every
vertex of B00 must be adjacent to every vertex of A0[A00. It remains to describe the edges
between vertices of A00 and vertices of B0. Since G contains no edges between vertices of A0
and vertices of B0, and every vertex of A00 is adjacent to every vertex of B00, the subgraph H
of G induced by A00[B0 is regular of degree d 12 . Since H is bipartite it is therefore obtained
from Kd+1
2 ;
d+1
2
by removing a perfect matching. Clearly the di erent versions of G obtained
by removing di erent perfect matchings in H are isomorphic.
39
6.2 On the Security Number of Qn
Then-cube, denotedQn, can be de ned inductively. LetQ0  = K1; thenQn = Qn 1 K2.
Note that jV(Qn)j = 2n and jE(Qn)j = n2n 1. Also note that Qn is an n-regular bipartite
graph. By examination, s(Q0) = s(Q1) = 1, and s(Q2) = 2. If the number of vertices of a
subgraph of Qn is known, Graham?s Density Lemma gives an upper bound on the number
of edges that subgraph may contain. It is used in the proofs of the results after it.
Graham?s Density Lemma ([7, 2]). Let G be a subgraph of Qn. Then jE(G)j  
1
2jV(G)jlog2jV(G)j, with equality if and only if G is isomorphic to Qm, for some m 2
f0;1;:::;ng.
Proposition 3. For n  1, su(Qn) = 2n 1, and the only minimum ultra-secure sets of
vertices induce subgraphs isomorphic to Qn 1.
Proof. Let S V(Qn) be ultra-secure. Since Qn is n-regular, the sum of the degrees of the
vertices of S is njSj. Applying the Theorem of Chapter 4.1 for ultra-security with X = S,
we have jSj Px2SjN[x] Sj. In other words, the number of edges with one end in S
and one end in N[S] S can be at most jSj. Let G be the subgraph of Qn induced by
S. Then Pv2SdG(v)  njSj jSj, and thus jE(G)j 12jSj(n 1). By Graham?s Lemma,
1
2jSj(n 1) 
1
2jSjlog2jSj, and so 2
n 1  jSj. If jSj= 2n 1, then jE(G)j= 2n 2(n 1) and
we have equality in Graham?s Density Lemma. Thus G is isomorphic to Qn 1. Then for
x2S, jN[x] Sj= 1. Letting each vertex of S defend itself, we see that S is ultra-secure.
Therefore, su(G) = 2n 1 and any minimum ultra-secure set of Qn must induce a subgraph
isormorphic to Qn 1.
Proposition 4. For n 1, 2bn2c s(Qn).
40
Proof. Let S  V(Qn) be secure. Let G be the subgraph of Qn induced by S. Then for
each v2S, 1 + dG(v) = jN[v]\Sj 12jN[v]j = 12(n + 1). Thus dG(v)   n 12  =  n2 . So
G must have at least 12jSj n2 edges. Applying Graham?s Lemma, 12jSj n2  12jSjlog2jSj,
which yields 2bn2c jSj.
Corollary. For n 1, 2bn2c s(Qn) s(F,I)(Qn) 2n 1.
41
Bibliography
[1] B. Bollob as and N. Th. Varopoulos, Representation of systems of measurable sets, Math.
Proc. Camb. Phil. Soc. 78 (1974), 323{325.
[2] B. Bre sar, W. Imrich, S. Klav zar, and B. Zmazek, Hypercubes as direct products, SIAM
J. Discrete Math. 18 (2005), 778{786.
[3] R. C. Brigham, R. D. Dutton, and S. T. Hedetniemi, Security in graphs, Discrete Appl.
Math. 155 (2007), 1708{1714.
[4] R. D. Dutton, On a graph?s security number, Discrete Math. 309 (2009), 4443{4447.
[5] , The evolution of a hard graph theory problem{secure sets, A course material of
COT 6410: Computational Complexity, Univesrity of Central Florida (2010), Available
at http://www.cs.ucf.edu/courses/cot6410/spr2010/doc/SecureSets.doc, Last
accessed April 4, 2012.
[6] R. D. Dutton, R. Lee, and R. C. Brigham, Bounds on a graph?s security number, Discrete
Appl. Math. 156 (2008), 695{704.
[7] R. L. Graham, On primitive graphs and optimal vertex assignments, Ann. New York
Acad. Sci. 75 (1970), 170{186.
[8] P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935), 26{30.
[9] P. R. Halmos and H. E. Vaughan, The marriage problem, Amer. J. Math. 72 (1950),
214{215.
[10] G. Isaak, P. D. Johnson, and C. Petrie, Integer and fractional security in graphs, Discrete
Appl. Math. 160 (2012), 2060{2062.
[11] P. D. Johnson Jr. and C. Petrie, Problem 8, Alabama Journal of Mathematics 35
(Spring/Fall 2010).
[12] K. Kozawa, Y. Otachi, and K. Yamazaki, Security number of grid-like graphs, Discrete
Appl. Math. 157 (2009), 2555{2561.
[13] P. Kristiansen, S. M. Hedetniemi, and S. T. Hedetniemi, Alliances in graphs, J. Combin.
Math. Combin. Comput. 48 (2004), 157{177.
[14] R. Rado, A theorem on general measure functions, Proc. London Math. Soc. 44 (1938),
61{91.
42
Appendices
43
Appendix A
An Alternative Proof that (I,I)-security Implies (F,F)-security
The notation here is as in Chapter 2. This proof predates the more elegant proof in-
cluded in Chapter 2. It essentially follows the proof of Theorem BDH by Brigham et al [3].
Theorem. Let G = (V;E) be a graph and S  V. If S is (I,I)-secure, then S is (F,F)-
secure.
Let S  S0  V. Let A be an attack on S0 such that A (v) = 0 for all v 2S0 S.
Let A = fs2S0jA (s) > D (s)g. Note that if s2S0 S, then s =2A , because A (s) =
0 D (s). A best defense of S is a defense D such that Ps2A A (s) D (s) is minimized.
Assume in these best defenses, that every defending vertex sends out its entire unit of defense;
that is, for v2S0, and any best defense D, Pu2N[v]\SD(v;u) = 1. An attack A is defendable
if there is a defense D for which Ps2A A (s) D (s) = 0; that is, A =;.
If D is a best defense, another best defense D0 can be found through one of two possible
transformations. For i2S0 such that D (i) >A (i) and j2S0,
1) If D(j;i) > 0, de ne  1(i;j) = minfD(j;i);D (i) A (i)g. Reduce D(j;i) by  1(i;j)
and increase D(j;j) by  1(i;j).
2) If D(i;i) > 0 and D(j;i) = 0, de ne  2(i) = minfD(i;i);D (i) A (i)g. Reduce
D(i;i) by  2(i) and increase D(i;j) by  2(i).
(Note that for both transformations, j must satisfy D (j) A (j), or D would not be
a best defense.)
Given a best defense D, let D be the set consisting of D and every defense that can
be derived from D by repeated applications of transformations 1) and 2). Note that if
D (u)  A (u) for some D 2 D, then D (u)  A (u) for all D 2 D. Let V +  S0 be
44
V + =fv2S0jD (v) >A (v) for some D2Dg. Let X = S0 V +.
Lemma 1. Let x2X, v 2S0. Then D(v;x) = D0(v;x) and D(x;v) = D0(x;v), for all
defenses D0 in D.
Proof. Let  ; 02D such that  0 is obtained from  by one of the transformations. If
x2X is involved in transformation 1) or 2), then it must play the role of j, because i2V +,
and x =2 V +. So after the transformation ( 0) (x) >   (x). Note that   (x)  A (x)
because x =2V +. If   (x) = A (x), then after the transformation, ( 0) (x) > A (x), and
x2V +, a contradiction. If   (x) <A (x), then after the transformation, A (x)   (x) >
A (x) ( 0) (x), contradicting that  is a best defense.
Lemma 2. Let  2D. Every s2N[X]\S0 satis es  (s;v) = 0 for v2V + = S0 X.
Proof. Let s2X. Suppose that  (s;v) > 0, for some v2V +. Since v2V +, there is a
 02D such that ( 0) (v) >A(v). Applying transformation 1) with i = v and j = s would
result in a new defense  00 with  00(s;s) >  0(s;s), contradicting Lemma 1.
Now let s2 (N[X]\S0) X. Note that s2V +. Suppose that  (s;y) > 0 for some
y2V +. Now s must have a neighbor x2X and by the  rst part of this proof,  (x;s) = 0.
We can assume   (y) > A (y) (y 2V +, so   (y)  A (y): If   (y) = A (y), a series of
transformations will result in a a defense D0 such that (D0) (y) >A (y). The vertex y does
not play the role of i, because i already satis es   (i) > A (i): If y = j and s = i, then
in either transformation, s still sends defense to y afterwards). Applying transformation 1)
with j = s and i = y results in a defense  0 such that ( 0) (s) > A (s). (We started with
  (s)  A (s).) Now apply transformation 2) with j = x and i = s. This results in a
defense  00 where  00(s;x) >  0(s;x), contradicting Lemma 1.
45
Suppose that S0 is not defendable from an attack A, where A (v) = 0 for all v2S0 S.
Let V + and X be as above and let X0 = X\S. If v 2 X X0, then A (v) = 0 and
so D (v) = 0, because v =2V +. So by Lemma 2, for any s2N[X]\S0, v 2N[s] X0,
D(s;v) = 0. In other words, all the defense power of N[X]\S0 is sent into X0. We have
jN[X]\S0j=
X
x2X0
D (x) <
X
x2X
A (x) =
X
x2X
X
v2N[X] S0
A(v;x)
=
X
v2N[X] S0
X
x2X
A(v;x) 
X
v2N[X] S0
1 =jN[X] S0j:
Thus there is an X S0 such that jN[X]\S0j<jN[X] S0j. Lemma 3, below, states
this result.
Lemma 3 Let G = (V;E) be a graph and S S0 V. Let A be an attack on S0, such that
for v2S0 S, A (v) = 0. If there is no successful defense of A, then there is an X  S
such that jN[X]\S0j<jN[X] S0j.
Letting S = S0 in Lemma 3, shows that if S is not (F,F)-secure, then there exists an
X S, such that jN[X]\Sj<jN[X] Sj, and the Theorem follows.
46
Appendix B
A Table of Security Numbers
G s(G) s(F,I)(G) su(G)
Pn 1 1 1
Cn 2 2 2
Fn 2 1 + n2 1 + n2 
n 2
Wn 3 1 + n+12  1 + n+12  
n 4
Pm Pn minfm;n;3g minfm;n;4g minfm;n;4g
Kn  n2 n 1 n 1
n 2
Km;n  m+n2  m+ n2 minfm+n 2;m+
l
m(n 1)
m+1
m
g
2 m n, n6= 2
Kn1;:::;nk  n2 n  nk2  n 
j
n
n nk+1
k
k 3, n = Pki=1ni;
nk = max1 i kfnig
Table B.1: Security Numbers
47