In this paper, we study two applications of graph minor reduction. In the first part of the paper, we introduce a variant of the boxicity, called strong boxicity, where the rectangular representation satisfies an additional condition that each rectangle contains at least one point not present in any other rectangle. We show how the strong boxicity of a graph can be estimated in terms of the strong boxicity of a minor and the number of edit operations needed to obtain from . In the second part of the paper, we consider false data injection (attack) in a flow graph and quantify the subsequent efect on the state of edges of via the edge variation factor . We use minor reduction techniques to obtain bounds on in terms of the connectivity parameters of , when the attacker has complete knowledge of and also discuss stealthy attacks with partial knowledge of the flow graph.
boxicity in terms of boxicity and estimate the strong boxicity of a general graph in terms of the strong boxicity of a minor and the number of edit operations needed to obtain the minor.
Flow graphs are expected to play an important role in the future as more and more systems
are being automated through software. This also leads to potential vulnerabilities as software
defined networks are themselves prone to attack and therefore it is important to study malicious
data attacks on such automated flow networks. A typical example is that of a power grid where
power flow through transmission lines is often subject to stealthy attacks (see for example, [
Flow graphs also frequently arise in the analysis of control systems [
In the second part of the paper, we are interested in studying how stealthy attacks afect the state of edges in a general flow graph. Diferent edges are afected diferently and we quantify this efect via the edge variation factor. In our main result Theorem 2 below, we estimate the maximum possible edge variation factor in terms of connectivity parameters of the flow graph, when the attacker has complete knowledge of the flow graph. In Section 5, we also discuss possibility of attacks with partial flow graph knowledge.
The paper is organized as follows. In Section 2, we define the concept of strong boxicity and determine bounds for strong boxicity in terms of boxicity and also given examples of graphs with strong boxicity exactly equal to 2. Next in Section 3, we show how strong boxicity of a graph can be estimated in terms of the strong boxicity of a minor and the number of edit operations needed to obtain the corresponding minor. In Section 4, we state and prove our main result Theorem 2 regarding existence of stealthy attacks in general flow graphs and in Section 5, we discuss stealthy attacks in the presence of partial information.
Let R denote the real line and for integer ≥ 1 define a rectangle ⊂ R to be a closed set of the form ∏︀=1[, ] ⊂ R, where ≤ are real numbers. We define 0 := ∏︀=1(, ) to be the interior of the rectangle where (, ) denotes the open interval with endpoints and and Set := ∖ 0 to be the boundary of the rectangle . Also for > 0, ∈ R, we let (, ) := + [︀ − 2 , 2 ]︀ be the − dimensional square of side length centred at .
Let = (, ) be a graph with vertex set = {1, 2, . . . , } and define (, ) ∈ to be the edge with endvertices and .
Definition 1. We say that a set of rectangles {}1≤ ≤ in R, ≥ 1 is a strong rectangular representation of if the following two conditions hold: (1) For any 1 ≤ ̸= ≤ , the rectangles (2) For every 1 ≤ ≤ , there exists a point ∈ and a number > 0 such that ∩ ̸= ∅ if and only if (, ) ∈ .
⎛ (, ) ⊂ ⎝
⋃︁ 1≤ ̸=≤
⎞
In other words, we prefer that no rectangle has its boundary covered completely by the remaining rectangles. The strong boxicity of denoted by () is defined to be the smallest integer such that both the conditions (1) − (2) hold. In Figure 1, we illustrate condition (2) with a example involving a strong rectangular representation in R2. The solid rectangle is , the point = and the dotted rectangle corresponds to (, ).
We recall that the boxicity denoted by () is defined to be smallest integer such that
condition (1) alone holds [
From the discussion in the above paragraph, we deduce that any connected graph containing
at least two edges must have strong boxicity at least two. In the following result, we give
examples of graphs whose strong boxicity is exactly 2 and also obtain bounds for the strong
boxicity in terms of the boxicity. We begin with some definitions. A tree is a connected graph
containing vertices and − 1 edges for some ≥ 2. A clique in a graph is a complete
subgraph of . We say that ℐ is a stable set in if no two vertices are adjacent in . The
graph with vertex set {1, 2, . . . , + } is called a threshold graph [
From (2.4), we see that any bound for boxicity can also be used to estimate the strong boxicity.
Therefore using () ≤ min(, ) where is the number of edges of [
Proof of Proposition 1: First, we see that any tree or threshold graph containing at least three vertices has strong boxicity of exactly two.
Trees: We prove by induction on , the number of vertices in the tree. For = 3 the tree 3 contains two edges, say (1, 2) and (2, 3). To see that (3) = 2, we define 1, 2 and 3 to be squares such that 1 and 3 are disjoint and 2 intersects both 1 and 3 partially, as shown in Figure 1().
Now, let +1 be a tree with vertex set {1, 2, . . . , + 1} and suppose the vertex + 1 is a leaf attached to the vertex ∈ := +1 ∖ { + 1}. The tree has strong boxicity two by induction assumption and so there exists a strong rectangular representation {}1≤ ≤ ⊂ R2 of . Moreover, there exists a vertex ∈ and a real number > 0 satisfying (2.2). Setting +1 := 2 (︀ , )︀ , we get that {}1≤ ≤ +1 forms a strong rectangular representation 2 of +1.
This is illustrated in Figure 1(), where = intersects other rectangles in the rectangular representation. However, the point = and a small surrounding neighbourhood is unique to . The rectangle +1 = intersecting only is shown in dotted lines.
Threshold graphs: Let = (, ) be any threshold graph with = {1, 2, . . . , } being a clique of size and = { + 1, . . . , + } being a stable set. Because of the nested neighbourhood property (2.3), we assume that ( + ) = {1, 2, . . . , } for some ≥ 1 ≥ 2 ≥ . . . ≥ ≥ 1.
For 1 ≤ ≤ , let be the 1 × rectangle in R2 centred at the origin. The rectangles {}1≤ ≤ form a strong representation of . We then let +1, . . . , + be small disjoint rectangles with the property that + intersects only the rectangles 1, . . . , and no other rectangle; this is illustrated in Figure 2 for the case = {1, 2, 3, 4} and = {5, 6} having neighbourhoods (5) = {1, 2, 3} and (6) = {1, 2}. The rectangles with corners labelled , 1 ≤ ≤ 4 form the strong rectangular representation of . The rectangles labelled 5 and 6 are 5 and 6, respectively. This completes the proof that any threshold graph containing at least three vertices has a strong boxicity of exactly two.
In the rest of the proof we prove (2.4). We use the following boundary relation throughout. For integer ≥ 1 let = ∏︀=1[, ] ⊂ R be any rectangle and let be its boundary. We then have that ⊇ − 1 × [, ]. (2.5) Indeed, writing = ∖ 0 = − 1 × [, ] ∖ 0− 1 × (, ) and using − 1 × [, ] = (︀ 0− 1 ∪ − 1︀) × [, ] ⊇
0− 1 × (, ) ⋃︁ − 1 × [, ], we get (2.5).
To prove (2.4), we let {}1≤ ≤ ⊂ R, = () be a rectangular representation of . For 1 ≤ ≤ , we define the rectangle := × [0, ] × [, ] and show first that {}1≤ ≤ ⊂ R+2 forms a rectangular representation of . Indeed if (, ) is an edge in then ∩ ̸= ∅ and so ∩ = ( ∩ ) × [0, min(, )] × [max(, ), ] ̸= ∅.
To see that the rectangles {} form a strong rectangular representation of the graph , we let ∈ be any vertex and let ∈ be any point in the boundary of . Setting := (, , ) we have from (2.5) that ∈ . Also ∈/ for any ̸= . Letting := 14 , we also get that no point of +2(, ) belongs to ⋃︀1≤ ̸=≤ . Therefore () ≤ () + 2 and this proves (2.4).
In this subsection, we estimate the strong boxicity of a graph by “converting" into a graph with small strong boxicity through appropriate edit operations. Formally, a deletion operation on is either a vertex deletion or edge deletion and a contraction operation is defined as follows. Let = (, ) be an edge in for some 1 ≤ ≤ − 1. The graph obtained by contracting the edge has vertex set {1, 2, . . . , − 1} and still has all edges not containing as an endvertex. In addition, in the graph , the vertex is now adjacent to every vertex of () ∖ {}. Henceforth, we denote a deletion operation or a contraction as an edit operation.
The graph obtained from an edit operation on as described above, is called a minor of . We say that a minor is obtained from after 1 vertex deletions, 2 edge deletions and 3 contractions if there are graphs = 0, 1, 2, . . . , = , = 1 + 2 + 3 such that is obtained by either a vertex deletion, edge deletion or contraction of − 1 and the total number of vertex deletions is 1 and the total number of edge deletions is 2. We have the following result regarding the strong boxicity.
Theorem 1. If is a minor that is obtained from after vertex deletions and edge deletions, then () − ≤ () ≤ () + + . (3.1) (3.2) (3.3) (3.4)
If is a minor that is obtained from after vertex deletions, edge deletions and contractions, then
() ≤ ( ) + + + 2 .
Moreover both (3.1) and (3.2) hold with strong boxicity (.) replaced by boxicity (.).
In practice, we choose to be a known graph with low strong boxicity. As an example, suppose is a connected graph on vertices having + edges. We pick and remove + 1 edges from to get a tree , whose strong boxicity is two by proposition 1. From relation (3.1) in theorem 1, we therefore get that () ≤ + 3.
It sufices to prove Theorem 1 for a single edit operation and we consider the three cases vertex deletion, edge deletion and edge contraction separately below. Also we prove for strong boxicity throughout and an analogous analysis holds for boxicity.
Vertex deletion: We show that for any vertex ∈ , the strong boxicity where = ∖ {} is the graph obtained by removing the vertex ∈ . We prove for = and an analogous analysis holds for every other vertex. If ℐ = {}1≤ ≤ ⊂ R, = () is a strong rectangular representation of satisfying (2.1), then ℐ ∖ {} is a strong rectangular representation of ∖ {} and so the first inequality in (3.3) is true.
For the second inequality, we let () be the neighbours of in and let {}1≤ ≤ − 1 ⊂
R, = () be a strong rectangular representation of with = ∏︀
=1[,, ,].
Setting := max, , and = min, , we define the rectangles {}1≤ ≤ ⊂ R+1
as
:=
⎨⎧ ×× [[20,, 53]]
⎩ [, 3] × [
for = . () ≤ () ≤ () + 1, By construction, the rectangles {}1≤ ≤ form a rectangular representation of . We now use (2.5) to see that {} also form a strong rectangular representation of . Indeed for ∈/ {} ∪ (), we let ∈ and > 0 be such that (, ) ⊂ ⎝ ⎛
⋃︁ 1≤ ̸=≤
⎞ ⎠ .
From the first line in (3.4) and (2.5) we get that := (, 0) ∈ and from (3.5) and the
second and third lines in (3.4) we further get
Therefore choosing smaller if necessary we get
+ (0, ) × [
⋃︁ 1≤ ̸=≤
⎞
If ∈ () then letting be as in (3.5), we choose = (, 2). Arguing as before and choosing smaller if necessary, we get (3.7). Finally, if = , then we choose to be the ( + 1)-tuple (3, . . . , 3, 6) so that ∈ . Setting = and using the definition of we again get (3.7). Thus the strong boxicity () ≤ + 1.
Edge deletion: For any edge = (, ) ∈ we show that
() − 1 ≤ () ≤ () + 1, where = ∖ {} is the graph obtained by removing the edge .
To prove the lower bound in (3.8), we let {}1≤ ≤ ⊂ R, = () be a strong rectangular
representation of . We define the rectangles {}1≤ ≤ ⊂ R+1 as follows:
:=
⎧ × [
Arguing as in the vertex deletion case, we get that the rectangles {}1≤ ≤ form a strong rectangular representation of and so the strong boxicity () ≤ + 1.
For the upper bound in (3.8), we use the fact that the graph has vertices and let 1, . . . , ⊂ R, = () be a strong rectangular representation of . As before if = ∏︀ =1[,, ,] then we set := max, , and := min, ,.
Letting () be the neighbours of in , we now define the rectangles {}1≤ ≤ ⊂ R+1
as follows:
:=
⎧
⎨
× [
for = . (3.5) (3.6) (3.7) (3.8) Arguing as in the vertex deletion case, we get that the rectangles {}1≤ ≤ form a strong rectangular representation of and so the strong boxicity () ≤ + 1.
Edge contraction: We now consider the remaining case where is the graph obtained by the contracting the edge = (, ) ∈ to the vertex ∈ and show that () ≤ () + 2.
The graph has − 1 vertices and we let {}1≤ ≤ − 1 ⊂ R, = (), be a strong
rectangular representation of . If () and () are the neighbours of and respectively
in , then ∈ () and ∈ () and we define the rectangles {}1≤ ≤ ⊂ R+2 as follows:
:=
⎪⎧ × [
× [
(3.9) (3.10)
We first argue that the rectangles {}1≤ ≤ form a rectangular representation of . Let (, ) be an edge not in . If (, ) is not of the form = , ∈ ()∖ () or = , ∈ ()∖ (), then the edge (, ) is not present in as well and so ∩ = ∅. Consequently ∩ = ∅.
If = and ∈ () ∖ (), then by definition of contraction we have that (, ) ∈ and so ∩ ̸= ∅. But from the first and fourth lines in (3.10), we get that ∩ = ∅. Similarly if = and ∈ () ∖ (), then ∩ = ∩ ̸= ∅. But from the second and third lines in (3.10) we get that ∩ = ∅.
Next let (, ) be an edge present in . If , ̸= or , then (, ) ∈ and so ∩ ̸= ∅. From the last three lines of (3.10) we then get that
∩ ⊇ ( ∩ ) × [
If = and = ∈ (), then from the first two lines of (3.10) we get that
∩ = × [
∩ = ( ∩ ) × [
Finally if = and ∈ () ∖ {} then using the fact that ∩ ̸= ∅ and the second and fourth lines in (3.10), we get that
∩ ⊃ ( ∩ ) × [
This proves the rectangles {} for a rectangular representation of .
To see that {} in fact form a strong rectangular representation, it sufices to see that (2.2) in condition (2) holds for = and = . Using the fact that {} ⊂ R form a strong rectangular representation of , we let ∈ R and > 0 be such that (, ) ⊂ ⎛ ⎝
⋃︁ 1≤ ̸=≤ − 1
⎞ ⎠ . Using the first and second lines of (3.10), we then set := (, 0, 3) and := (, 10, 6) respectively and choose smaller if necessary to get ⎛
⎞ +2(, ) ⊂ ⎝
⋃︁ 1≤ ̸=≤ ⎠ and +2(, ) ⊂ ⎝ ⎛
⋃︁ 1≤ ≤ − 1
⎞ ⎠ .
By (2.5), we have that ∈ and ∈ and so () ≤ + 2.
Finally, in Figure 3, we pictorially represent a possible choice for the rectangles in R2 that can be used to construct a strong rectangular representation for as follows: The rectangle with corners labelled ∈ {, } is used for the vertex and so we set = × . Similarly, the rectangle 1 with corners labelled 1 is for neighbours of that are not adjacent to and the rectangle 2 with corners labelled 2 is for neighbours of that are not adjacent to . For the rest of the vertices, we pick any rectangle 0 that is adjacent all the rectangles in Figure 3. Defining the appropriate rectangles , 1 ≤ ≤ , we then get a strong rectangular representation of in R+2.
Proof of Theorem 1: Follows from (3.3), (3.8) and (3.9).
A flow graph is a graph = (, ) with vertex set = {1, 2, . . . , } and edge set (which we index as { + 1, . . . , }) along with the following additional properties: The state of the system is given by a real valued vector x = [1, . . . , ] where denotes the state of vector . An edge with index joining vertices and is assigned a gain , = , > 0 and the flow through the edge from to is given by , ( − ) = h · x, (4.1) where h is the 1 × vector with exactly two non-zero entries: , in ℎ position and − , in the ℎ position. The net flow into the vertex equals the sum of flows from all edges connected for all 1 ≤ ≤ .
Given the flow vector H · x, the gain matrix H and a reference state (say 1), it is possible to calculate the overall state x : We first use (4.1) to get − across every edge (, ) ∈ . We then calculate the states of all vertices adjacent to the vertex 1 and then iteratively calculate the states of the rest of the vertices.
We see how the diferential state calculation procedure described above can be afected by stealthy attacks. For a subset ℱ of edges in , we define a ℱ − attack vector or simply an attack vector to be a × 1 vector a = [1, . . . , ] satisfying ̸= 0 if and only if the index corresponds to an edge in ℱ or is a vertex adjacent to an edge in ℱ .
We say that ℱ is stealthily attackable if there exists an attack vector a of the form a = H · s for some × 1 vector s = [1, . . . , ] . For convenience, we denote a = H · s to be a stealthy attack vector and denote s to be the ℱ − stealth vector or simply the stealth vector corresponding to the attack vector a. In other words, we say that an attack vector a is stealthy if a is also a lfow vector.
By definition the attack vector a afects only edges of ℱ or vertices adjacent to edges of ℱ . From the flow equation (4.1), we therefore have that − ̸= 0 if and only if the edge (, ) of with endvertices and belongs to ℱ . Given the corrupted flow vector H · x + H · s, the diferential state calculation procedure described before obtains the diference between the values of the states at vertices and to be
From (4.4), we have that diferent edges in ℱ are afected diferently due to stealthy attacks and so we define the edge variation factor (ℱ ) as ︂{ ( − ) + ( − ) if edge (, ) ∈ ℱ
( − ) otherwise. (ℱ ) := inf s min(,)∈ℱ | − | max(,)∈ℱ | − | to and is given by ∑︁ , ( − ) = ∑︁ , − ∼ ∼ ∑︁ , = h · x, ∼ (4.2) with ∼ denoting that vertices and are connected by an edge in . The 1 × vector h has values − , for positions 1 ≤ ̸= ≤ , ∼ and has the value , = ∑︀∼ ,. All other entries of h are zero. Letting H = [h1 , . . . , h ] be the × gain matrix, we then have ∑︁ , = 0 =1 where the infimum is taken over all ℱ − stealth vectors s. The edge variation factor measures the variation in the corruption of the state vector x due to stealthy attacks.
We have the following result regarding the variation factor of stealthy attacks on ℱ . (4.3) (4.4) (4.5) Theorem 2. The set of edges ℱ is stealthily attackable if and only if for every cycle ∈ , either ∩ ℱ = ∅ or # ∩ ℱ ≥ 2. Moreover, if ℱ is stealthily attackable, then 1 ≤ (ℱ ) ≤ (ℱ ) − 1, (4.6) where (ℱ ) is the number of components in the graph ∖ ℱ obtained after removing the edges in ℱ .
A single edge is stealthily attackable if and only if it is a bridge; i.e., removal of the edge results in disconnection of the graph into two distinct components.
In general, stealthily attacking multiple “non-critical" edges whose disconnection results in few components, creates a more “uniform" corruption across the attacked edges. Therefore from the designer perspective, it would be beneficial to have extra protection in these non-critical edges.
Suppose ℱ is stealthily attackable and there exists a cycle such that # ∩ ℱ = 1; i.e., there exists exactly one edge = (, ) ∈ present in ℱ . We arrive at a contradiction as follows. Let a = H · s be the stealthy attack vector on ℱ and let s = [1, . . . , ] be the corresponding stealth vector. As argued prior to (4.4), we have that − ̸= 0 if and only if (, ) ∈ ℱ . Thus ̸= .
Denoting the cycle = (, 1, 2, . . . , , , ), we then have that the edge (, 1) ∈/ ℱ and so = 1 . Similarly (1, 2) ∈/ ℱ and so 1 = 2 . Continuing this way, we get = 1 = 2 = . . . = . Finally, the edge (, ) is also not in ℱ and so = = , a contradiction.
Conversely, suppose every cycle in contains either zero or at least two edges of ℱ . We now use minor reduction to obtain the desired stealth vector, by extracting appropriate components of that allow the vector construction. The details are as follows. First we remove the edges in ℱ to get = (ℱ ) connected components 1, . . . , of . Every edge = (, ) ∈ satisfies the following property:
The edge ∈ ℱ if and only if the vertices ∈ 1 and ∈ 1 belong to distinct components 1 ̸= 1 .
Indeed, by construction, we have that if the vertices and belong to distinct components 1 and 1 , then the edge (, ) necessarily belongs to ℱ . Conversely if (, ) ∈ ℱ and both and were to belong to the same component , then and would be connected by a path in . This in turn would imply that ∪ is a cycle in containing only one edge of ℱ , a contradiction.
We now construct the stealth vector s = [1, . . . , ] as follows. Let > 0 be a real number to be determined later. For a vertex ∈ we set = ( ) = − 1, if ∈ , 1 ≤ ≤ so that s( ) = [1( ), . . . , ( )]. Letting a = H · s we first argue that = 0 if is neither a vertex adjacent to some edge of ℱ nor the index of some edge in ℱ . Indeed if is the index of (4.7) (4.8) ∑︁ , = 0.
=2 where and for 2 ≤ ≤ the term is the sum of the gains of edges adjacent to the vertex and present in the component so that an edge (, ) ∈/ ℱ then both and belong to the same component 0 for some 1 ≤ 0 ≤ (property (4.7)). This implies that = = 0− 1 and so from (4.1), we get that || = ,| − | = 0.
Next if is a vertex and the vertex is not the endvertex of any edge in ℱ , then by property (4.7) all neighbours of are present in the same component 0 for some 1 ≤ 0 ≤ . This implies that = = 0− 1 for every neighbour of and from (4.2), we again get that = 0.
We now see that ̸= 0 if either is the index of some edge (, ) ∈ ℱ or is a vertex adjacent to some edge of ℱ . First suppose that is the index of (, ) ∈ ℱ . From property (4.7) above, we have that and belong to distinct components 1 ̸= 1 and so by construction = 1− 1 ̸= 1− 1 = .
From (4.1), this implies that || = ,| − | ̸= 0.
Finally, choosing appropriately, we now show that ̸= 0 if is a vertex adjacent to some edge in ℱ . Suppose the vertex belongs to the component 1 for some 1 ≤ 1 ≤ so that the corresponding entry = 1− 1. Since is the endvertex of some edge in ℱ , we have from property (4.7) that has at least one neighbour outside 1 . Let 1 , . . . , be the set of all components containing either or a neighbour of . Using the flow equation (4.2) we then get that
Let Λ be the finite set of the roots of the equation () = 0 so that 1 ∈ Λ by (4.10) and set Λ = ⋃︀ Λ, where the union is taken over all vertices adjacent to an edge in ℱ . Choosing /∈ Λ we have that ( ) ̸= 0 and since is arbitrary this implies that a( ) = H · s( ) is a stealthy attack vector.
From (4.8) and property (4.7), we also get for any edge (, ) ∈ ℱ that the corresponding diference |( )− ( )| is of the form | 1 − 1 | for some distinct integers 1, 1 ≥ 0. Therefore if { }≥ 1, ∈/ Λ, < 1 is a sequence converging to one as → ∞ then using max |( ) − ( )| = 1 − − 1 and (,)∈ℱ
min |( ) − ( )| = − 2 − − 1 (,)∈ℱ
(4.9) (4.10) we get that max(,)∈ℱ |( ) − ( )| = min(,)∈ℱ |( ) − ( )| as → ∞. This implies that (ℱ ) ≤ (ℱ ) − 1 and completes the proof of Theorem 2.
In this section, we extend the result of Theorem 2 in two directions. In the first subsection, we use the structure of the graph ∖ ℱ to improve the bound for the edge variation factor and in the second subsection, we study stealthy attacks with partial information.
We now describe a slight modification of the proof of Theorem 2 to obtain stealth vectors with
lesser variation. Consider the component graph = (, ) constructed as follows:
We represent the component by a node ∈ and connect nodes and if there
exists an edge ∈ ℱ with one endvertex in and other endvertex in . A proper colouring
of using ≥ 1 colours is a map : → {1, 2, . . . , } such that () ̸= () if
vertices and are adjacent in . The chromatic number 0 of is the smallest
integer such that admits a proper colouring using colours [
Letting 0 : → {1, 2, . . . , 0} be a proper colouring of using 0 colours, we define the stealth vector y = [1, . . . , ] as follows. If 0() = , we assign = ( ) = − 1 for all vertices ∈ . Finally, letting y = [1, . . . , ] , we set c = H · y.
To see that c is a stealthy attack vector, we consider any edge (, ) ∈ with index . If and belong to the same component in {}, then − = 0 and so we have from (4.1) that the corresponding entry = ,( − ) = 0. Similarly if a vertex is not adjacent to any edge in ℱ then using property (4.7) as before, we get that all neighbours of belong to the same component in {} as . As before, we use (4.2) to get that the corresponding entry = 0.
If an edge (, ) ∈ ℱ then by property (4.7), the vertices ∈ 1 and ∈ 1 belong to distinct components 1 ̸= 1 . In the graph constructed above, the nodes 1 and 1 are joined by an edge and so have diferent colours (1 ) ̸= (1 ). This in turn implies that ̸= and so = ,( − ) ̸= 0, by (4.1).
Finally, for a vertex adjacent to an edge in ℱ , we argue as in (4.9) to get the corresponding polynomial expression for ( ). The expressions here have diferent degrees than in (4.9) and therefore diferent set of roots. Again we choose an appropriate sequence { } converging to one so that as → ∞. This implies that (ℱ ) ≤ 0 − 1.
In this subsection, we see how stealth attacks could possibly be carried out with coarse information regarding the gain matrix H. This situation arises for example, when measurement noise results in imperfect estimates of the gain values.
Suppose the attacker does not exactly know the true gains {, } but knows that 1 ≤ , ≤ 2 for some positive finite constants 1, 2. for a vertex adjacent to some edge in ℱ . Indeed from (4.9), we have that
We construct the stealth vector s as follows. For a vertex ∈ , we choose as in (4.8) and get from the proof of Theorem 2 that = 0 if is neither the index of an edge in ℱ nor is a vertex adjacent to any edges in ℱ . Moreover ̸= 0 if is the index of an edge of ℱ . The knowledge of edge gains is required only to determine an appropriate value of so that ̸= 0 (5.1) (5.2) = (, H) = 1, · 1− 1 − =2 ∑︁ , · − 1 where the positive { ,} are as in (4.9). = (, 1, 2) not depending on the choice of H. Indeed, assuming 1 > 2 . . . > in (5.2) and using (5.1) we have
We now see that if > 0 is chosen large, then || ≥ for some constant so that || ≥ 1 1− 1
· 2 ︂) − 1 · 1− ≥ 1 1− 1 ︂( 1
· 2 − 1 · 1− ︂) (5.3) large we have from (5.3) that where = (ℱ ) is the number of components of ∖ℱ . The final relation in (5.3) is true because, the number of distinct powers of in the stealth vector s is . Thus for all ≥ 0(, , 1, 2) > 1 || ≥ 1 1− 1 2 ≥ 1 2 .
Choosing > 1 = 1(, 1, 2) large enough, we get that || ≥ to some edge in ℱ . This obtains our desired stealth vector s = s( ). 21 for all vertices adjacent
As a concluding remark, we state here that though the attack as described is possible, the edge variation (ℱ ) could be quite large and therefore be possibly detected. In this paper, we have studied two applications of graph minor reduction in boxicity and stealthy attacks on flowgraphs. We have used minor reduction recursively to estimate the boxicity of an arbitrary graph. Similarly, we used a component reduction technique to determine necessary and suficient conditions that allows stealthy attacks in a flowgraph.
In the above, we have considered deterministic graphs. In the future, we plan to incorporate and study analogous problems in random graphs.
I thank Professors V. Raman, C. R. Subramanian and the referee for crucial comments that led to an improvement of the paper. I also thank IMSc for my fellowships.