Copyright for this paper by its authors. Use permitted under Creative Commons
License Attribution 4.0 International (CC BY 4.0).

Algorithms, Computing and Mathematics Conference (ACM 2021), Chennai, India

<EMAIL_ADDRESS>]

# Two Applications of Graph Minor Reduction

Ghurumuruhan Ganesan  Institute of Mathematical Sciences, HBNI, Chennai

(2021)

###### Abstract

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 $G$ can be
estimated in terms of the strong boxicity of a minor $H$ and the number of
edit operations needed to obtain $H$ from $G.$ In the second part of the
paper, we consider false data injection (attack) in a flow graph $G$ and
quantify the subsequent effect on the state of edges of $G$ via the _edge
variation factor_ $\theta.$ We use minor reduction techniques to obtain bounds
on $\theta$ in terms of the connectivity parameters of $G,$ when the attacker
has complete knowledge of $G$ and also discuss stealthy attacks with partial
knowledge of the flow graph.

###### keywords:

Strong boxicity Minor reduction Flow graphs Stealthy attacks Edge variation
factor

##  1 Introduction

Graph minor reduction is an important problem from both theoretical and
application perspectives. In particular, graph minor reduction algorithms are
extensively used in computer science to solve a variety of problems related to
network routing and design. For a detailed survey of algorithmic aspects of
graph minor reduction, we refer to the survey [2].

In this paper, we study two theoretical applications of graph minor reduction
in estimating the strong boxicity of an arbitrary graph and determining
conditions for stealthy attacks on flow graphs. Below we discuss these two
issues in that order.

### Strong Boxicity

The boxicity of a graph $G$ [12] is the smallest integer $k$ such that $G$
admits a rectangular representation in $\mathbb{R}^{k},$ where $\mathbb{R}$
denotes the real line. Boxicity as defined above is finite and is no more than
the total number of vertices in $G.$ Since then many bounds for boxicity has
been obtained in terms of various graph parameters including treewidth [4] and
maximum degree [5, 6] and also in terms of poset dimension [1, 13].

In the first part of the paper, we define a variant of boxicity which we call
strong boxicity where we impose the additional condition that no rectangle
corresponding to a particular vertex is covered by the rectangles
corresponding to the other vertices. We find bounds for strong 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.

### Stealthy Attacks in Flow Graphs

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, [9]). The survey by [8] also describes various aspects of cyber-
physical attacks and defence strategies on the smart grid, from a network
layer perspective.

Flow graphs also frequently arise in the analysis of control systems [10, 7]
where the node variables could be either electrical (like for example
voltages, currents etc,) or mechanical (like position, angle etc.) in nature.
Detection of false data injection (either unintentional or intentional) is
crucial here as well and steps must be taken to ensure that the measurements
are as authentic as possible.

In the second part of the paper, we are interested in studying how stealthy
attacks affect the state of edges in a general flow graph. Different edges are
affected differently and we quantify this effect 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.

##  2 Strong boxicity

Let $\mathbb{R}$ denote the real line and for integer $d\geq 1$ define a
rectangle $A\subset\mathbb{R}^{d}$ to be a closed set of the form
$\prod_{i=1}^{d}[a_{i},b_{i}]\subset\mathbb{R}^{d},$ where $a_{i}\leq b_{i}$
are real numbers. We define $A^{0}:=\prod_{i=1}^{n}(a_{i},b_{i})$ to be the
interior of the rectangle $A$ where $(a_{i},b_{i})$ denotes the open interval
with endpoints $a_{i}$ and $b_{i}$ and Set $\partial A:=A\setminus A^{0}$ to
be the boundary of the rectangle $A.$ Also for $y>0,x\in\mathbb{R}^{d},$ we
let $B_{d}(x,y):=x+\left[-\frac{y}{2},\frac{y}{2}\right]^{d}$ be the
$d-$dimensional square of side length $y$ centred at $x.$

Let $G=(V,E)$ be a graph with vertex set $V=\\{1,2,\ldots,n\\}$ and define
$(i,j)\in E$ to be the edge with endvertices $i$ and $j.$

######  Definition 1.

We say that a set of rectangles $\\{I_{i}\\}_{1\leq i\leq n}$ in
$\mathbb{R}^{d},d\geq 1$ is a _strong rectangular representation_ of $G$ if
the following two conditions hold:
$(c1)$ For any $1\leq i\neq j\leq n,$ the rectangles

$I_{i}\cap I_{j}\neq\emptyset\text{ if and only if }(i,j)\in E.$ (2.1)

$(c2)$ For every $1\leq v\leq n,$ there exists a point $x_{v}\in\partial
I_{v}$ and a number $a_{v}>0$ such that

$B_{d}(x_{v},a_{v})\subset\left(\bigcup_{1\leq u\neq v\leq
n}I_{u}\right)^{c}.$ (2.2)

In other words, we prefer that no rectangle has its boundary covered
completely by the remaining rectangles. The _strong boxicity_ of $G$ denoted
by $s(G)$ is defined to be the smallest integer $d$ such that both the
conditions $(c1)-(c2)$ hold. In Figure 1, we illustrate condition $(c2)$ with
a example involving a strong rectangular representation in $\mathbb{R}^{2}.$
The solid rectangle $ABCD$ is $I_{v},$ the point $X=x_{v}$ and the dotted
rectangle corresponds to $B_{d}(x_{v},a_{v}).$

(a)

(b)

Figure 1: $(a)$ The condition $(c2)$ ensures that each rectangle has an
exclusive boundary point and a small surrounding neighbourhood. $(b)$ Strong
rectangular representation of the graph $H$ with vertex set $\\{1,2,3\\}$ and
edge set $\\{(1,2),(2,3)\\}.$

We recall that the boxicity $G$ denoted by $b(G)$ is defined to be smallest
integer $d$ such that condition $(c1)$ alone holds [12]. By definition we
therefore have $b(G)\leq s(G).$ To see that strong boxicity is not always
equal to boxicity, we consider the graph $H$ with vertex set $\\{1,2,3\\}$ and
edge set $\\{(1,2),(2,3)\\}.$ Setting $J_{1}=[0,2],J_{2}=[1,4]$ and
$J_{3}=[2,5],$ we see that condition $(c1)$ in definition 1 holds and so
$b(H)=1.$ However, condition $(c2)$ does not hold and so $s(H)\geq 2.$
Considering $J_{1},J_{2}$ and $J_{3}$ to be squares such that $J_{1}$ and
$J_{3}$ are disjoint and $J_{2}$ intersects both $J_{1}$ and $J_{3}$
partially, as shown in Figure 1$(b),$ we get that $s(H)=2.$

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 $n$
vertices and $n-1$ edges for some $n\geq 2.$ A _clique_ in a graph $G$ is a
complete subgraph of $G.$ We say that ${\cal I}$ is a _stable_ set in $G$ if
no two vertices are adjacent in $G.$ The graph $G$ with vertex set
$\\{1,2,\ldots,n+r\\}$ is called a _threshold graph_ [11] if $G$ contains a
clique $K$ with vertex set $\\{1,2,\ldots,n\\}$ and a stable set
$I=\\{n+1,\ldots,n+r\\}$ satisfying the following nested neighbourhood
property: If ${\cal N}(v)$ is the set of all neighbours of $v$ in the graph
$G,$ then

${\cal N}(n+1)\supseteq{\cal N}(n+2)\supseteq\ldots\supseteq{\cal N}(n+r).$
(2.3)

######  Proposition 1.

If $G$ is a tree or a threshold graph containing at least three vertices, then
the strong boxicity $s(G)=2.$ In general, for any graph $G$ we have that

$b(G)\leq s(G)\leq b(G)+2.$ (2.4)

From (2.4), we see that any bound for boxicity can also be used to estimate
the strong boxicity. Therefore using $b(G)\leq\min(m,n)$ where $m$ is the
number of edges of $G$ [12], we get from (2.4) that $s(G)\leq\min(m,n)+2.$

_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 $n,$ the number of vertices in the tree.
For $n=3$ the tree $T_{3}$ contains two edges, say $(1,2)$ and $(2,3).$ To see
that $s(T_{3})=2,$ we define $J_{1},J_{2}$ and $J_{3}$ to be squares such that
$J_{1}$ and $J_{3}$ are disjoint and $J_{2}$ intersects both $J_{1}$ and
$J_{3}$ partially, as shown in Figure 1$(b)$.

Now, let $T_{n+1}$ be a tree with vertex set $\\{1,2,\ldots,n+1\\}$ and
suppose the vertex $n+1$ is a leaf attached to the vertex $v\in
T_{n}:=T_{n+1}\setminus\\{n+1\\}.$ The tree $T_{n}$ has strong boxicity two by
induction assumption and so there exists a strong rectangular representation
$\\{J_{i}\\}_{1\leq i\leq n}\subset\mathbb{R}^{2}$ of $T_{n}.$ Moreover, there
exists a vertex $x_{v}\in J_{v}$ and a real number $a_{v}>0$ satisfying (2.2).
Setting $J_{n+1}:=B_{2}\left(x_{v},\frac{a_{v}}{2}\right),$ we get that
$\\{J_{i}\\}_{1\leq i\leq n+1}$ forms a strong rectangular representation of
$T_{n+1}.$

This is illustrated in Figure 1$(a),$ where $J_{v}=EFGH$ intersects other
rectangles in the rectangular representation. However, the point $X=x_{v}$ and
a small surrounding neighbourhood is unique to $J_{v}.$ The rectangle
$J_{n+1}=ABCD$ intersecting only $J_{v}$ is shown in dotted lines.

_Threshold graphs_ : Let $G=(K,I)$ be any threshold graph with
$K=\\{1,2,\ldots,n\\}$ being a clique of size $n$ and $I=\\{n+1,\ldots,n+r\\}$
being a stable set. Because of the nested neighbourhood property (2.3), we
assume that $N(n+i)=\\{1,2,\ldots,l_{i}\\}$ for some $n\geq l_{1}\geq
l_{2}\geq\ldots\geq l_{r}\geq 1.$

Figure 2: Strong rectangular representation of a threshold graph.

For $1\leq i\leq n,$ let $J_{i}$ be the $\frac{1}{i}\times i$ rectangle in
$\mathbb{R}^{2}$ centred at the origin. The rectangles $\\{J_{i}\\}_{1\leq
i\leq n}$ form a strong representation of $K.$ We then let
$J_{n+1},\ldots,J_{n+r}$ be small disjoint rectangles with the property that
$J_{n+i}$ intersects only the rectangles $J_{1},\ldots,J_{l_{i}}$ and no other
rectangle; this is illustrated in Figure 2 for the case $K=\\{1,2,3,4\\}$ and
$I=\\{5,6\\}$ having neighbourhoods ${\cal N}(5)=\\{1,2,3\\}$ and ${\cal
N}(6)=\\{1,2\\}.$ The rectangles with corners labelled $i,1\leq i\leq 4$ form
the strong rectangular representation of $K.$ The rectangles labelled $5$ and
$6$ are $J_{5}$ and $J_{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 $d\geq 1$ let
$U_{d}=\prod_{i=1}^{d}[a_{i},b_{i}]\subset\mathbb{R}^{d}$ be any rectangle and
let $\partial U_{d}$ be its boundary. We then have that

$\partial U_{d}\supseteq\partial U_{d-1}\times[a_{d},b_{d}].$ (2.5)

Indeed, writing $\partial U_{d}=U_{d}\setminus
U^{0}_{d}=U_{d-1}\times[a_{d},b_{d}]\setminus U^{0}_{d-1}\times(a_{d},b_{d})$
and using

$\displaystyle U_{d-1}\times[a_{d},b_{d}]$ $\displaystyle=$
$\displaystyle\left(U_{d-1}^{0}\cup\partial U_{d-1}\right)\times[a_{d},b_{d}]$
$\displaystyle\supseteq$ $\displaystyle
U_{d-1}^{0}\times(a_{d},b_{d})\bigcup\partial U_{d-1}\times[a_{d},b_{d}],$

we get (2.5).

To prove (2.4), we let $\\{I_{i}\\}_{1\leq i\leq
n}\subset\mathbb{R}^{b},b=b(G)$ be a rectangular representation of $G.$ For
$1\leq i\leq n,$ we define the rectangle $J_{i}:=I_{i}\times[0,i]\times[i,n]$
and show first that $\\{J_{i}\\}_{1\leq i\leq n}\subset\mathbb{R}^{b+2}$ forms
a rectangular representation of $G.$ Indeed if $(i,j)$ is an edge in $G$ then
$I_{i}\cap I_{j}\neq\emptyset$ and so

$J_{i}\cap J_{j}=(I_{i}\cap
I_{j})\times[0,\min(i,j)]\times[\max(i,j),n]\neq\emptyset.$

To see that the rectangles $\\{J_{i}\\}$ form a strong rectangular
representation of the graph $G,$ we let $v\in G$ be any vertex and let
$x_{v}\in\partial I_{v}$ be any point in the boundary of $I_{v}.$ Setting
$y_{v}:=(x_{v},v,v)$ we have from (2.5) that $y_{v}\in\partial J_{v}.$ Also
$y_{v}\notin J_{u}$ for any $u\neq v.$ Letting $a_{v}:=\frac{1}{4},$ we also
get that no point of $B_{b+2}(y_{v},a_{v})$ belongs to $\bigcup_{1\leq i\neq
v\leq n}J_{i}.$ Therefore $s(G)\leq b(G)+2$ and this proves (2.4). ∎

##  3 Minor Reduction

In this subsection, we estimate the strong boxicity of a graph $G$ by
“converting" $G$ into a graph $H$ with small strong boxicity through
appropriate edit operations. Formally, a _deletion operation_ on $G$ is either
a vertex deletion or edge deletion and a contraction operation is defined as
follows. Let $e=(u,n)$ be an edge in $G$ for some $1\leq u\leq n-1.$ The graph
$H$ obtained by _contracting_ the edge $e$ has vertex set
$\\{1,2,\ldots,n-1\\}$ and still has all edges not containing $n$ as an
endvertex. In addition, in the graph $H,$ the vertex $u$ is now adjacent to
every vertex of $N_{G}(n)\setminus\\{u\\}.$ Henceforth, we denote a deletion
operation or a contraction as an _edit operation_.

The graph $H$ obtained from an edit operation on $G$ as described above, is
called a _minor_ of $G.$ We say that a minor $H$ is obtained from $G$ after
$a_{1}$ vertex deletions, $a_{2}$ edge deletions and $a_{3}$ contractions if
there are graphs
$G=H_{0},H_{1},H_{2},\ldots,H_{r}=H,r=a_{1}+a_{2}+a_{3}$ such that $H_{i}$ is
obtained by either a vertex deletion, edge deletion or contraction of
$H_{i-1}$ and the total number of vertex deletions is $a_{1}$ and the total
number of edge deletions is $a_{2}.$ We have the following result regarding
the strong boxicity.

######  Theorem 1.

If $H$ is a minor that is obtained from $G$ after $\alpha_{v}$ vertex
deletions and $\alpha_{e}$ edge deletions, then

$s(H)-\alpha_{e}\leq s(G)\leq s(H)+\alpha_{v}+\alpha_{e}.$ (3.1)

If $F$ is a minor that is obtained from $G$ after $\beta_{v}$ vertex
deletions, $\beta_{e}$ edge deletions and $\beta_{c}$ contractions, then

$s(G)\leq s(F)+\beta_{v}+\beta_{e}+2\beta_{c}.$ (3.2)

Moreover both (3.1) and (3.2) hold with strong boxicity $s(.)$ replaced by
boxicity $b(.).$

In practice, we choose $H$ to be a known graph with low strong boxicity. As an
example, suppose $G$ is a connected graph on $n$ vertices having $n+r$ edges.
We pick and remove $r+1$ edges from $G$ to get a tree $H,$ whose strong
boxicity is two by proposition 1. From relation (3.1) in theorem 1, we
therefore get that $s(G)\leq r+3.$

It suffices 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 $v\in G,$ the strong boxicity

$s\left(F_{v}\right)\leq s(G)\leq s\left(F_{v}\right)+1,$ (3.3)

where $F_{v}=G\setminus\\{v\\}$ is the graph obtained by removing the vertex
$v\in G.$ We prove for $v=n$ and an analogous analysis holds for every other
vertex. If ${\cal I}=\\{I_{i}\\}_{1\leq i\leq n}\subset\mathbb{R}^{s},s=s(G)$
is a strong rectangular representation of $G$ satisfying (2.1), then ${\cal
I}\setminus\\{I_{n}\\}$ is a strong rectangular representation of
$G\setminus\\{n\\}$ and so the first inequality in (3.3) is true.

For the second inequality, we let $N(n)$ be the neighbours of $n$ in $G$ and
let $\\{J_{i}\\}_{1\leq i\leq n-1}\subset\mathbb{R}^{k},k=s\left(F_{n}\right)$
be a strong rectangular representation of $F_{n}$ with
$J_{i}=\prod_{l=1}^{k}[a_{i,l},b_{i,l}].$ Setting $M_{up}:=\max_{i,l}b_{i,l}$
and $M_{low}=\min_{i,l}a_{i,l}$ we define the rectangles $\\{I_{w}\\}_{1\leq
w\leq n}\subset\mathbb{R}^{k+1}$ as

$I_{w}:=\left\\{\begin{array}[]{cc}J_{w}\times[0,3]&\text{ for
}w\notin\\{n\\}\cup N(n)\\\ J_{w}\times[2,5]&\text{ for }w\in N(n)\\\
\left[M_{low},3M_{up}\right]^{k}\times[4,6]&\text{ for
}w=n.\end{array}\right.$ (3.4)

By construction, the rectangles $\\{I_{i}\\}_{1\leq i\leq n}$ form a
rectangular representation of $G.$ We now use (2.5) to see that $\\{I_{i}\\}$
also form a strong rectangular representation of $G.$ Indeed for
$w\notin\\{n\\}\cup N(n),$ we let $x_{w}\in\partial J_{w}$ and $a_{w}>0$ be
such that

$B_{k}(x_{w},a_{w})\subset\left(\bigcup_{1\leq u\neq w\leq
n}J_{u}\right)^{c}.$ (3.5)

From the first line in (3.4) and (2.5) we get that
$y_{w}:=(x_{w},0)\in\partial I_{w}$ and from (3.5) and the second and third
lines in (3.4) we further get

$y_{w}+B_{k}(0,a_{w})\times[-1,1]\subset\left(\bigcup_{1\leq u\neq w\leq
n}I_{u}\right)^{c}.$ (3.6)

Therefore choosing $a_{w}$ smaller if necessary we get

$B_{k+1}(y_{w},a_{w})\subset\left(\bigcup_{1\leq u\neq w\leq
n}I_{u}\right)^{c}.$ (3.7)

If $w\in N(n)$ then letting $x_{w}$ be as in (3.5), we choose
$y_{w}=(x_{w},2).$ Arguing as before and choosing $a_{w}$ smaller if
necessary, we get (3.7). Finally, if $w=n,$ then we choose $y_{w}$ to be the
$(k+1)$-tuple $(3M_{up},\ldots,3M_{up},6)$ so that $y_{w}\in\partial I_{w}.$
Setting $a_{w}=M_{up}$ and using the definition of $M_{up}$ we again get
(3.7). Thus the strong boxicity $s(G)\leq k+1.$

_Edge deletion_ : For any edge $e=(u,v)\in G$ we show that

$s\left(H_{e}\right)-1\leq s(G)\leq s\left(H_{e}\right)+1,$ (3.8)

where $H_{e}=G\setminus\\{e\\}$ is the graph obtained by removing the edge
$e.$

To prove the lower bound in (3.8), we let $\\{I_{i}\\}_{1\leq i\leq
n}\subset\mathbb{R}^{s},s=s(G)$ be a strong rectangular representation of $G.$
We define the rectangles $\\{A_{i}\\}_{1\leq i\leq n}\subset\mathbb{R}^{s+1}$
as follows:

$A_{i}:=\left\\{\begin{array}[]{cc}I_{i}\times[0,4]&\text{ for }i\neq u,v\\\
I_{i}\times[1,2]&\text{ for }i=u\\\ I_{i}\times[3,5]&\text{ for
}i=v.\end{array}\right.$

Arguing as in the vertex deletion case, we get that the rectangles
$\\{A_{i}\\}_{1\leq i\leq n}$ form a strong rectangular representation of
$H_{e}$ and so the strong boxicity $s\left(H_{e}\right)\leq s+1.$

For the upper bound in (3.8), we use the fact that the graph $H_{e}$ has $n$
vertices and let $L_{1},\ldots,L_{n}\subset\mathbb{R}^{r},r=s(H_{e})$ be a
strong rectangular representation of $H_{e}.$ As before if
$L_{i}=\prod_{l=1}^{r}[a_{i,l},b_{i,l}]$ then we set
$W_{up}:=\max_{i,l}b_{i,l}$ and $W_{low}:=\min_{i,l}a_{i,l}.$

Letting $N_{e}(v)$ be the neighbours of $v$ in $H_{e},$ we now define the
rectangles $\\{R_{i}\\}_{1\leq i\leq n}\subset\mathbb{R}^{r+1}$ as follows:

$R_{i}:=\left\\{\begin{array}[]{cc}L_{i}\times[0,3]&\text{ for
}i\notin\\{u,v\\}\cup N_{e}(v)\\\ L_{i}\times[2,5]&\text{ for }i\in\\{u\\}\cup
N_{e}(v)\\\ \left[W_{low},3W_{up}\right]^{r}\times[4,6]&\text{ for
}i=v.\end{array}\right.$

Arguing as in the vertex deletion case, we get that the rectangles
$\\{R_{i}\\}_{1\leq i\leq n}$ form a strong rectangular representation of $G$
and so the strong boxicity $s(G)\leq r+1.$

_Edge contraction_ : We now consider the remaining case where $G_{e}$ is the
graph obtained by the contracting the edge $e=(u,n)\in G$ to the vertex $u\in
G_{e}$ and show that

$s(G)\leq s(G_{e})+2.$ (3.9)

The graph $G_{e}$ has $n-1$ vertices and we let $\\{S_{i}\\}_{1\leq i\leq
n-1}\subset\mathbb{R}^{q},q=s(G_{e}),$ be a strong rectangular representation
of $G_{e}.$ If $N(u)$ and $N(n)$ are the neighbours of $u$ and $n$
respectively in $G,$ then $n\in N(u)$ and $u\in N(n)$ and we define the
rectangles $\\{T_{i}\\}_{1\leq i\leq n}\subset\mathbb{R}^{q+2}$ as follows:

$T_{i}:=\left\\{\begin{array}[]{cc}S_{u}\times[0,6]\times[3,7]&\text{ for
}i=u\\\ S_{u}\times[4,10]\times[6,10]&\text{ for }i=n\\\
S_{i}\times[0,10]\times[0,5]&\text{ for }i\in N(u)\setminus\left(\\{n\\}\cup
N(n)\right)\\\ S_{i}\times[8,10]\times[0,10]&\text{ for }i\in
N(n)\setminus\left(\\{u\\}\cup N(u)\right)\\\
S_{i}\times[0,10]\times[0,10]&\text{ otherwise }.\end{array}\right.$ (3.10)

We first argue that the rectangles $\\{T_{i}\\}_{1\leq i\leq n}$ form a
rectangular representation of $G.$ Let $(i,j)$ be an edge not in $G.$ If
$(i,j)$ is not of the form $i=u,j\in N(n)\setminus N(u)$ or $i=n,j\in
N(u)\setminus N(n),$ then the edge $(i,j)$ is not present in $G_{e}$ as well
and so $S_{i}\cap S_{j}=\emptyset.$ Consequently $T_{i}\cap T_{j}=\emptyset.$

If $i=u$ and $j\in N(n)\setminus N(u),$ then by definition of contraction we
have that $(u,j)\in G_{e}$ and so $S_{u}\cap S_{j}\neq\emptyset.$ But from the
first and fourth lines in (3.10), we get that $T_{u}\cap T_{j}=\emptyset.$
Similarly if $i=n$ and $j\in N(u)\setminus N(n),$ then $S_{i}\cap
S_{j}=S_{u}\cap S_{j}\neq\emptyset.$ But from the second and third lines in
(3.10) we get that $T_{i}\cap T_{j}=\emptyset.$

Next let $(i,j)$ be an edge present in $G.$ If $i,j\neq u$ or $n,$ then
$(i,j)\in G_{e}$ and so $S_{i}\cap S_{j}\neq\emptyset.$ From the last three
lines of (3.10) we then get that

$T_{i}\cap T_{j}\supseteq(S_{i}\cap
S_{j})\times[8,10]\times[0,5]\neq\emptyset.$

If $i=u$ and $j=n\in N(u),$ then from the first two lines of (3.10) we get
that

$T_{u}\cap T_{n}=S_{u}\times[4,6]\times[6,7]\neq\emptyset.$ (3.11)

If $i=u$ and $j\in N(u)\setminus(\\{n\\}\cup N(n))$ then $S_{u}\cap
S_{j}\neq\emptyset$ and so from the first and third lines in (3.10), we get
that

$T_{u}\cap T_{j}=(S_{u}\cap S_{j})\times[0,6]\times[3,5]\neq\emptyset.$

Finally if $i=n$ and $j\in N(n)\setminus\\{u\\}$ then using the fact that
$S_{u}\cap S_{j}\neq\emptyset$ and the second and fourth lines in (3.10), we
get that

$T_{n}\cap T_{j}\supset(S_{u}\cap
S_{j})\times[8,10]\times[6,10]\neq\emptyset.$

This proves the rectangles $\\{T_{i}\\}$ for a rectangular representation of
$G.$

To see that $\\{T_{i}\\}$ in fact form a strong rectangular representation, it
suffices to see that (2.2) in condition $(c2)$ holds for $v=u$ and $v=n.$
Using the fact that $\\{S_{i}\\}\subset\mathbb{R}^{s}$ form a strong
rectangular representation of $G_{e},$ we let $x_{u}\in\mathbb{R}^{s}$ and
$a_{u}>0$ be such that

$B_{q}(x_{u},a_{u})\subset\left(\bigcup_{1\leq i\neq u\leq
n-1}S_{i}\right)^{c}.$

Using the first and second lines of (3.10), we then set $y_{u}:=(x_{u},0,3)$
and $y_{n}:=(x_{u},10,6)$ respectively and choose $a_{u}$ smaller if necessary
to get

$B_{q+2}(y_{u},a_{u})\subset\left(\bigcup_{1\leq i\neq u\leq
n}T_{i}\right)^{c}\text{ and }B_{q+2}(y_{n},a_{u})\subset\left(\bigcup_{1\leq
i\leq n-1}T_{i}\right)^{c}.$

By (2.5), we have that $y_{u}\in\partial T_{u}$ and $y_{n}\in\partial T_{n}$
and so $s(G_{e})\leq q+2.$

Figure 3: Rectangles used in constructing a strong rectangular representation
for $G.$

Finally, in Figure 3, we pictorially represent a possible choice for the
rectangles in $\mathbb{R}^{2}$ that can be used to construct a strong
rectangular representation for $G$ as follows: The rectangle $L_{x}$ with
corners labelled $x\in\\{u,n\\}$ is used for the vertex $x$ and so we set
$T_{x}=S_{x}\times L_{x}.$ Similarly, the rectangle $L_{1}$ with corners
labelled $1$ is for neighbours of $u$ that are not adjacent to $n$ and the
rectangle $L_{2}$ with corners labelled $2$ is for neighbours of $n$ that are
not adjacent to $v.$ For the rest of the vertices, we pick any rectangle
$L_{0}$ that is adjacent all the rectangles in Figure 3. Defining the
appropriate rectangles $T_{i},1\leq i\leq n,$ we then get a strong rectangular
representation of $G$ in $\mathbb{R}^{b+2}.$ ∎

_Proof of Theorem 1_: Follows from (3.3), (3.8) and (3.9). ∎

##  4 Stealthy Attacks on Flow Graphs

A flow graph is a graph $G=(V,E)$ with vertex set $V=\\{1,2,\ldots,n\\}$ and
edge set $E$ (which we index as $\\{n+1,\ldots,t\\}$) along with the following
additional properties: The state of the system is given by a real valued
vector $\mathbf{x}=[x_{1},\ldots,x_{n}]^{T}$ where $x_{i}$ denotes the state
of vector $i.$ An edge with index $f$ joining vertices $i$ and $j$ is assigned
a _gain_ $B_{i,j}=B_{j,i}>0$ and the _flow_ through the edge $f$ from $j$ to
$i$ is given by

$B_{i,j}(x_{i}-x_{j})=\mathbf{h}_{f}\cdot\mathbf{x},$ (4.1)

where $\mathbf{h}_{f}$ is the $1\times n$ vector with exactly two non-zero
entries: $B_{i,j}$ in $i^{th}$ position and $-B_{i,j}$ in the $j^{th}$
position. The _net_ flow into the vertex $i$ equals the sum of flows from all
edges connected to $i$ and is given by

$\sum_{j\sim i}B_{i,j}(x_{i}-x_{j})=x_{i}\sum_{j\sim i}B_{i,j}-\sum_{j\sim
i}B_{i,j}x_{j}=\mathbf{h}_{i}\cdot\mathbf{x},$ (4.2)

with $j\sim i$ denoting that vertices $j$ and $i$ are connected by an edge in
$G.$ The $1\times n$ vector $\mathbf{h}_{i}$ has values $-B_{i,j}$ for
positions $1\leq j\neq i\leq n,j\sim i$ and has the value $H_{i,i}=\sum_{u\sim
i}B_{i,u}.$ All other entries of $\mathbf{h}_{i}$ are zero. Letting
$\mathbf{H}=[\mathbf{h}_{1}^{T},\ldots,\mathbf{h}_{t}^{T}]^{T}$ be the
$t\times n$ gain matrix, we then have

$\sum_{j=1}^{n}H_{i,j}=0$ (4.3)

for all $1\leq i\leq t.$

Given the flow vector $\mathbf{H}\cdot\mathbf{x},$ the gain matrix
$\mathbf{H}$ and a reference state (say $x_{1}$), it is possible to calculate
the overall state $\mathbf{x}:$ We first use (4.1) to get $x_{i}-x_{j}$ across
every edge $(i,j)\in E.$ 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 differential state calculation procedure described above can be
affected by stealthy attacks. For a subset ${\cal F}$ of edges in $G,$ we
define a ${\cal F}-$_attack vector_ or simply an attack vector to be a
$t\times 1$ vector $\mathbf{a}=[a_{1},\ldots,a_{t}]^{T}$ satisfying $a_{l}\neq
0$ if and only if the index $l$ corresponds to an edge in ${\cal F}$ or is a
vertex adjacent to an edge in ${\cal F}.$

We say that ${\cal F}$ is _stealthily attackable_ if there exists an attack
vector $\mathbf{a}$ of the form $\mathbf{a}=\mathbf{H}\cdot\mathbf{s}$ for
some $n\times 1$ vector $\mathbf{s}=[s_{1},\ldots,s_{n}]^{T}.$ For
convenience, we denote $\mathbf{a}=\mathbf{H}\cdot\mathbf{s}$ to be a
_stealthy_ attack vector and denote $\mathbf{s}$ to be the ${\cal F}-$_stealth
vector_ or simply the stealth vector corresponding to the attack vector
$\mathbf{a}.$ In other words, we say that an attack vector $\mathbf{a}$ is
stealthy if $\mathbf{a}$ is also a flow vector.

By definition the attack vector $\mathbf{a}$ affects only edges of ${\cal F}$
or vertices adjacent to edges of ${\cal F}.$ From the flow equation (4.1), we
therefore have that $s_{i}-s_{j}\neq 0$ if and only if the edge $(i,j)$ of $G$
with endvertices $i$ and $j$ belongs to ${\cal F}.$ Given the corrupted flow
vector $\mathbf{H}\cdot\mathbf{x}+\mathbf{H}\cdot\mathbf{s},$ the differential
state calculation procedure described before obtains the difference between
the values of the states at vertices $i$ and $j$ to be

$\left\\{\begin{array}[]{cc}(x_{i}-x_{j})+(s_{i}-s_{j})&\text{ if edge
}(i,j)\in{\cal F}\\\ (x_{i}-x_{j})&\text{ otherwise}.\end{array}\right.$ (4.4)

From (4.4), we have that different edges in ${\cal F}$ are affected
differently due to stealthy attacks and so we define the _edge variation
factor_ $\theta({\cal F})$ as

$\theta({\cal F}):=\inf_{\mathbf{s}}\frac{\max_{(i,j)\in{\cal
F}}|s_{i}-s_{j}|}{\min_{(i,j)\in{\cal F}}|s_{i}-s_{j}|},$ (4.5)

where the infimum is taken over all ${\cal F}-$stealth vectors $\mathbf{s}.$
The edge variation factor measures the variation in the corruption of the
state vector $\mathbf{x}$ due to stealthy attacks.

We have the following result regarding the variation factor of stealthy
attacks on ${\cal F}.$

######  Theorem 2.

The set of edges ${\cal F}$ is stealthily attackable if and only if for every
cycle $C\in G,$ either $C\cap{\cal F}=\emptyset$ or $\\#C\cap{\cal F}\geq 2.$
Moreover, if ${\cal F}$ is stealthily attackable, then

$1\leq\theta({\cal F})\leq k({\cal F})-1,$ (4.6)

where $k({\cal F})$ is the number of components in the graph $G\setminus{\cal
F}$ obtained after removing the edges in ${\cal F}.$

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 $G$ 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.

### Proof of Theorem 2

Suppose ${\cal F}$ is stealthily attackable and there exists a cycle $C$ such
that
$\\#C\cap{\cal F}=1;$ i.e., there exists exactly one edge $e=(u,v)\in C$
present in ${\cal F}.$ We arrive at a contradiction as follows. Let
$\mathbf{a}=\mathbf{H}\cdot\mathbf{s}$ be the stealthy attack vector on ${\cal
F}$ and let $\mathbf{s}=[s_{1},\ldots,s_{n}]^{T}$ be the corresponding stealth
vector. As argued prior to (4.4), we have that $s_{i}-s_{j}\neq 0$ if and only
if $(i,j)\in{\cal F}.$ Thus $s_{u}\neq s_{v}.$

Denoting the cycle $C=(u,u_{1},u_{2},\ldots,u_{t},v,u),$ we then have that the
edge $(u,u_{1})\notin{\cal F}$ and so $s_{u}=s_{u_{1}}.$ Similarly
$(u_{1},u_{2})\notin{\cal F}$ and so $s_{u_{1}}=s_{u_{2}}.$ Continuing this
way, we get $s_{u}=s_{u_{1}}=s_{u_{2}}=\ldots=s_{u_{t}}.$ Finally, the edge
$(u_{t},v)$ is also not in ${\cal F}$ and so $s_{u}=s_{u_{t}}=s_{v},$ a
contradiction.

Conversely, suppose every cycle $C$ in $G$ contains either zero or at least
two edges of ${\cal F}.$ We now use minor reduction to obtain the desired
stealth vector, by extracting appropriate components of $G$ that allow the
vector construction. The details are as follows. First we remove the edges in
${\cal F}$ to get $k=k({\cal F})$ connected components ${\cal
C}_{1},\ldots,{\cal C}_{k}$ of $G.$ Every edge $e=(w,y)\in G$ satisfies the
following property:

The edge $e\in{\cal F}$ if and only if the vertices $w\in{\cal C}_{w_{1}}$ and
$y\in{\cal C}_{y_{1}}$ belong to distinct components ${\cal
C}_{w_{1}}\neq{\cal C}_{y_{1}}.$ (4.7)

Indeed, by construction, we have that if the vertices $w$ and $y$ belong to
distinct components ${\cal C}_{w_{1}}$ and ${\cal C}_{y_{1}},$ then the edge
$(w,y)$ necessarily belongs to ${\cal F}.$ Conversely if $(w,y)\in{\cal F}$
and both $w$ and $y$ were to belong to the same component ${\cal C}_{j},$ then
$w$ and $y$ would be connected by a path $P_{wy}$ in ${\cal C}_{j}.$ This in
turn would imply that $e\cup P_{wy}$ is a cycle in $G$ containing only one
edge $e$ of ${\cal F},$ a contradiction.

We now construct the stealth vector $\mathbf{s}=[s_{1},\ldots,s_{n}]$ as
follows. Let $\lambda>0$ be a real number to be determined later. For a vertex
$v\in G$ we set

$s_{v}=s_{v}(\lambda)=\lambda^{i-1},\text{ if }v\in{\cal C}_{i},\;\;\;\;1\leq
i\leq k$ (4.8)

so that $\mathbf{s}(\lambda)=[s_{1}(\lambda),\ldots,s_{n}(\lambda)].$ Letting
$\mathbf{a}=\mathbf{H}\cdot\mathbf{s}$ we first argue that $a_{l}=0$ if $l$ is
neither a vertex adjacent to some edge of ${\cal F}$ nor the index of some
edge in ${\cal F}.$ Indeed if $l$ is the index of an edge $(u,v)\notin{\cal
F}$ then both $u$ and $v$ belong to the same component ${\cal C}_{i_{0}}$ for
some $1\leq i_{0}\leq k$ (property (4)). This implies that
$s_{u}=s_{v}=\lambda^{i_{0}-1}$ and so from (4.1), we get that

$|a_{l}|=B_{u,v}|s_{u}-s_{v}|=0.$

Next if $l$ is a vertex and the vertex $l$ is not the endvertex of any edge in
${\cal F},$ then by property (4) all neighbours of $l$ are present in the same
component ${\cal C}_{j_{0}}$ for some $1\leq j_{0}\leq k.$ This implies that
$s_{w}=s_{l}=\lambda^{j_{0}-1}$ for every neighbour $w$ of $l$ and from (4.2),
we again get that $a_{l}=0.$

We now see that $a_{l}\neq 0$ if either $l$ is the index of some edge
$(w,y)\in{\cal F}$ or is a vertex adjacent to some edge of ${\cal F}.$ First
suppose that $l$ is the index of $(w,y)\in{\cal F}.$ From property (4) above,
we have that $w$ and $y$ belong to distinct components ${\cal
C}_{w_{1}}\neq{\cal C}_{y_{1}}$ and so by construction

$s_{w}=\lambda^{w_{1}-1}\neq\lambda^{y_{1}-1}=s_{y}.$

From (4.1), this implies that $|a_{l}|=B_{w,y}|s_{w}-s_{y}|\neq 0.$

Finally, choosing $\lambda$ appropriately, we now show that $a_{l}\neq 0$ if
$l$ is a vertex adjacent to some edge in ${\cal F}.$ Suppose the vertex $l$
belongs to the component ${\cal C}_{j_{1}}$ for some $1\leq j_{1}\leq k$ so
that the corresponding entry $s_{l}=\lambda^{j_{1}-1}.$ Since $l$ is the
endvertex of some edge in ${\cal F},$ we have from property (4) that $l$ has
at least one neighbour outside ${\cal C}_{j_{1}}.$ Let ${\cal
C}_{j_{1}},\ldots,{\cal C}_{j_{w}}$ be the set of all components containing
either $l$ or a neighbour of $l.$ Using the flow equation (4.2) we then get
that

$a_{l}=a_{l}(\lambda)=\beta_{1,l}\cdot\lambda^{j_{1}-1}-\sum_{r=2}^{w}\beta_{r,l}\cdot\lambda^{j_{r}-1}$
(4.9)

where

$\beta_{1,l}:=\sum_{q\sim l}B_{l,q}-\sum_{q\sim l,q\in{\cal
C}_{j_{1}}}B_{l,q}>0$

and for $2\leq r\leq w$ the term

$\beta_{r,l}:=\sum_{q\sim l,q\in{\cal C}_{j_{r}}}B_{l,q}>0$

is the sum of the gains of edges adjacent to the vertex $l$ and present in the
component ${\cal C}_{j_{r}}$ so that

$\beta_{1,l}-\sum_{r=2}^{w}\beta_{r,l}=0.$ (4.10)

Let $\Lambda_{l}$ be the finite set of the roots of the equation $a_{l}(x)=0$
so that $1\in\Lambda_{l}$ by (4.10) and set
$\Lambda_{tot}=\bigcup_{v}\Lambda_{v},$ where the union is taken over all
vertices adjacent to an edge in ${\cal F}.$ Choosing
$\lambda\notin\Lambda_{tot}$ we have that $a_{l}(\lambda)\neq 0$ and since $l$
is arbitrary this implies that
$\mathbf{a}(\lambda)=\mathbf{H}\cdot\mathbf{s}(\lambda)$ is a stealthy attack
vector.

From (4.8) and property (4), we also get for any edge $(i,j)\in{\cal F}$ that
the corresponding difference $|s_{i}(\lambda)-s_{j}(\lambda)|$ is of the form
$|\lambda^{i_{1}}-\lambda^{j_{1}}|$ for some distinct integers
$i_{1},j_{1}\geq 0.$ Therefore if $\\{\lambda_{q}\\}_{q\geq
1},\lambda_{q}\notin\Lambda_{tot},\lambda_{q}<1$ is a sequence converging to
one as $q\rightarrow\infty$ then using

$\max_{(i,j)\in{\cal
F}}|s_{i}(\lambda_{q})-s_{j}(\lambda_{q})|=1-\lambda_{q}^{k-1}\text{ and
}\min_{(i,j)\in{\cal
F}}|s_{i}(\lambda_{q})-s_{j}(\lambda_{q})|=\lambda_{q}^{k-2}-\lambda_{q}^{k-1}$

we get that

$\frac{\max_{(i,j)\in{\cal
F}}|s_{i}(\lambda_{q})-s_{j}(\lambda_{q})|}{\min_{(i,j)\in{\cal
F}}|s_{i}(\lambda_{q})-s_{j}(\lambda_{q})|}=\frac{1-\lambda_{q}^{k-1}}{\lambda_{q}^{k-2}(1-\lambda_{q})}\longrightarrow
k-1$ (4.11)

as $q\rightarrow\infty.$ This implies that $\theta({\cal F})\leq k({\cal
F})-1$ and completes the proof of Theorem 2. ∎

##  5 Extension of results in 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 $G\setminus{\cal F}$ to
improve the bound for the edge variation factor and in the second subsection,
we study stealthy attacks with partial information.

### Improved Bound for the Variation Factor

We now describe a slight modification of the proof of Theorem 2 to obtain
stealth vectors with lesser variation. Consider the component graph
$G_{comp}=(V_{comp},E_{comp})$ constructed as follows: We represent the
component ${\cal C}_{i}$ by a node $n_{i}\in V_{comp}$ and connect nodes
$n_{i}$ and $n_{j}$ if there exists an edge $e\in{\cal F}$ with one endvertex
in ${\cal C}_{i}$ and other endvertex in ${\cal C}_{j}.$ A proper colouring of
$G_{comp}$ using $a\geq 1$ colours is a map
$g:V_{comp}\rightarrow\\{1,2,\ldots,a\\}$ such that $g(v)\neq g(u)$ if
vertices $u$ and $v$ are adjacent in $G_{comp}.$ The chromatic number
$\chi_{0}$ of $G_{comp}$ is the smallest integer $z$ such that $G_{comp}$
admits a proper colouring using $z$ colours [3].

Letting $g_{0}:V_{comp}\rightarrow\\{1,2,\ldots,\chi_{0}\\}$ be a proper
colouring of $G_{comp}$ using $\chi_{0}$ colours, we define the stealth vector
$\mathbf{y}=[y_{1},\ldots,y_{n}]^{T}$ as follows. If $g_{0}(n_{i})=j,$ we
assign $y_{v}=y_{v}(\lambda)=\lambda^{j-1}$ for all vertices $v\in{\cal
C}_{i}.$ Finally, letting $\mathbf{y}=[y_{1},\ldots,y_{n}]^{T},$ we set
$\mathbf{c}=\mathbf{H}\cdot\mathbf{y}.$

To see that $\mathbf{c}$ is a stealthy attack vector, we consider any edge
$(u,v)\in G$ with index $l.$ If $u$ and $v$ belong to the same component in
$\\{{\cal C}_{i}\\},$ then $y_{u}-y_{v}=0$ and so we have from (4.1) that the
corresponding entry $c_{l}=B_{u,v}(y_{u}-y_{v})=0.$ Similarly if a vertex $u$
is not adjacent to any edge in ${\cal F}$ then using property (4) as before,
we get that all neighbours of $u$ belong to the same component in $\\{{\cal
C}_{i}\\}$ as $u.$ As before, we use (4.2) to get that the corresponding entry
$c_{u}=0.$

If an edge $(u,v)\in{\cal F}$ then by property (4), the vertices $u\in{\cal
C}_{u_{1}}$ and $v\in{\cal C}_{v_{1}}$ belong to distinct components ${\cal
C}_{u_{1}}\neq{\cal C}_{v_{1}}.$ In the graph $G_{comp}$ constructed above,
the nodes $n_{u_{1}}$ and $n_{v_{1}}$ are joined by an edge and so have
different colours $g(n_{u_{1}})\neq g(n_{v_{1}}).$ This in turn implies that
$y_{u}\neq y_{v}$ and so $c_{l}=B_{u,v}(y_{u}-y_{v})\neq 0,$ by (4.1).

Finally, for a vertex adjacent to an edge in ${\cal F},$ we argue as in (4.9)
to get the corresponding polynomial expression for $c_{l}(\lambda).$ The
expressions here have different degrees than in (4.9) and therefore different
set of roots. Again we choose an appropriate sequence $\\{\lambda_{q}\\}$
converging to one so that

$\frac{1-\lambda_{q}^{\chi_{0}-1}}{\lambda_{q}^{\chi_{0}-2}-\lambda_{q}^{\chi_{0}-1}}\longrightarrow\chi_{0}-1$

as $q\rightarrow\infty.$ This implies that $\theta({\cal F})\leq\chi_{0}-1.$

### Partial Knowledge

In this subsection, we see how stealth attacks could possibly be carried out
with coarse information regarding the gain matrix $\mathbf{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 $\\{B_{i,j}\\}$ but
knows that

$\epsilon_{1}\leq B_{i,j}\leq\epsilon_{2}$ (5.1)

for some positive finite constants $\epsilon_{1},\epsilon_{2}.$

We construct the stealth vector $\mathbf{s}$ as follows. For a vertex $v\in
G,$ we choose $s_{v}$ as in (4.8) and get from the proof of Theorem 2 that
$a_{l}=0$ if $l$ is neither the index of an edge in ${\cal F}$ nor is a vertex
adjacent to any edges in ${\cal F}.$ Moreover $a_{l}\neq 0$ if $l$ is the
index of an edge of ${\cal F}.$ The knowledge of edge gains is required only
to determine an appropriate value of $\lambda$ so that $a_{l}\neq 0$ for a
vertex $l$ adjacent to some edge in ${\cal F}.$ Indeed from (4.9), we have
that

$a_{l}=a_{l}(\lambda,\mathbf{H})=\beta_{1,l}\cdot\lambda^{j_{1}-1}-\sum_{r=2}^{w}\beta_{r,l}\cdot\lambda^{j_{r}-1}$
(5.2)

where the positive $\\{\beta_{r,l}\\}$ are as in (4.9).

We now see that if $\lambda>0$ is chosen large, then $|a_{l}|\geq D$ for some
constant
$D=D(\lambda,\epsilon_{1},\epsilon_{2})$ not depending on the choice of
$\mathbf{H}.$ Indeed, assuming
$j_{1}>j_{2}\ldots>j_{w}$ in (5.2) and using (5.1) we have

$\displaystyle|a_{l}|$ $\displaystyle=$
$\displaystyle\beta_{1,l}\lambda^{j_{1}-1}\left|1-\sum_{r=2}^{w}\frac{\beta_{r,l}}{\beta_{1,l}\cdot\lambda^{j_{1}-j_{r}}}\right|$
$\displaystyle\geq$
$\displaystyle\epsilon_{1}\lambda^{j_{1}-1}\left(1-\sum_{r=2}^{w}\frac{\epsilon_{2}}{\epsilon_{1}\cdot\lambda^{j_{1}-j_{r}}}\right)$

so that

$|a_{l}|\geq\epsilon_{1}\lambda^{j_{1}-1}\left(1-\frac{w\cdot\epsilon_{2}}{\epsilon_{1}\cdot\lambda^{j_{1}-j_{r}}}\right)\geq\epsilon_{1}\lambda^{j_{1}-1}\left(1-\frac{k\cdot\epsilon_{2}}{\epsilon_{1}\cdot\lambda^{j_{1}-j_{r}}}\right)$
(5.3)

where $k=k({\cal F})$ is the number of components of $G\setminus{\cal F}.$ The
final relation in (5.3) is true because, the number of distinct powers of
$\lambda$ in the stealth vector $\mathbf{s}$ is $k.$ Thus for all
$\lambda\geq\lambda_{0}(l,k,\epsilon_{1},\epsilon_{2})>1$ large we have from
(5.3) that

$|a_{l}|\geq\frac{\epsilon_{1}\lambda^{j_{1}-1}}{2}\geq\frac{\epsilon_{1}}{2}.$

Choosing $\lambda>\lambda_{1}=\lambda_{1}(k,\epsilon_{1},\epsilon_{2})$ large
enough, we get that $|a_{l}|\geq\frac{\epsilon_{1}}{2}$ for _all_ vertices $l$
adjacent to some edge in ${\cal F}.$ This obtains our desired stealth vector
$\mathbf{s}=\mathbf{s}(\lambda).$

As a concluding remark, we state here that though the attack as described is
possible, the edge variation $\theta({\cal F})$ could be quite large and
therefore be possibly detected. ∎

##  6 Conclusion and Future Work

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 sufficient
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.

###### Acknowledgements.

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.

## References

  * [1] A. Adiga, D. Bhowmick and L. S. Chandran, Boxicity and Poset Dimension, SIAM Journal of Discrete Mathematics, 25 (2011) 1687–1698.
  * [2] D. Bienstock, M. A. Langston, Chapter 8: Algorithmic Implications of the Graph Minor Theorem, Handbooks in Operations Research and Management Science, Elsevier, 7 (1995) 481–502.
  * [3] B. Bollobás, Modern Graph Theory, Springer, 1998.
  * [4] L. S. Chandran and N. Sivadasan, Boxicity and Treewidth, Journal of Combinatorial Theory, Series B, 97 (2007) 733–744.
  * [5] L. S. Chandran, M. C. Francis and N. Sivadasan, Boxicity and maximum degree,  Journal of Combinatorial Theory, Series B, 98(2008) 443–445.
  * [6] L. Esperet, Boxicity of graphs with bounded degree, European Journal of Combinatorics, 30 (2009) 1277–1280.
  * [7] H. Fawzi, P. Tabuada and S. Diggavi, Secure estimation and control for cyber-physical systems under adversarial attacks, IEEE Transactions on Automatic Control, 59(2014) 1454–1467.
  * [8] H. He and J. Yan, Cyber-physical attacks and defences in the smart grid: a survey,IET Cyber-Physical Systems: Theory and Applications, 1(2016) 13–27.
  * [9] O. Kosut, L. Jia, R. J. Thomas and L. Tong, Malicious data attacks on the smart grid, IEEE Transactions on Smart Grid, 2(2011), 645–658.
  * [10] B. Kuo, Automatic control systems, Prentice Hall, 1995.
  * [11] N. V. R. Mahadev and U. N. Peled, Threshold graphs and related topics, North Holland, First Edition, 1995.
  * [12] F. S. Roberts, On the boxicity and cubicity of a graph, Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968) Academic Press, New York, 1969, pp. 301–310.
  * [13] A. Scott and D. R. Wood, Better bounds for poset dimension and boxicity, Transactions of the American Mathematical Society, (2019), https://doi.org/10.1090/tran/7962.