# On Edge Pruning of Communication Networks under an Age-of-Information Framework
## 3 Proposed Model
### Series-Parallel Networks  
In this work, we restrict our study to consider topologies of the network to be exclusively series-parallel topologies. Despite this restriction, the general approach can be applied to any topology. However, the network reduction that is studied later in this work can not be done unless it is a series-parallel network. This class of topologies arises naturally in many communication network applications [28]. Following we demonstrate briefly the definition of a series-parallel graph (graph means a general multigraph in this context) with the basic operations for constructing such graphs. The definition follows the convention of [PERSON] in [29].  
First, we need to name a more general class of graphs that is referred to as two-terminal graphs, which are any connected graphs with exactly two unique nodes called the source node \(s\) and the destination node \(d\)--that is, the simplest two-terminal graph is a pair of source-destination nodes linked through one edge.  
The first graphs-composition operation is composition in parallel \(C_{p}\) operation that performs on exactly two operands, a two-terminal graph \(G_{1}\) and another two-terminal graph \(G_{2}\). The composed graph \(G_{p}=C_{p}(G_{1},G_{2})\) is another two-terminal graph that is the disjoint union of graphs \(G_{1}\) and \(G_{2}\) after unifying the source nodes of \(G_{1}\) and \(G_{2}\) to form the source node of \(G_{p}\), and unifying the destination nodes of \(G_{1}\) and \(G_{2}\) to form the destination node of \(G_{p}\) as well. Note that \(C_{p}(G_{1},G_{2})=C_{p}(G_{2},G_{1})\). An example is demonstrated in Figure 1a.  
Figure 1: (**a**) The operation composition in parallel denoted by \(C_{p}\). (**b**) The operation composition in series denoted by \(C_{s}\). (**c**) a sample SP graph that is represented as three parallel paths: \(P1\|P2\|P3\), where \(P1\): \([1,2\|3,[4,5\|6][\|7,8\|],9]\). \(P2\): \([10\|11,12]\). \(P3\): \([13]\).  
The second graphs-composition operation is composition in series \(C_{s}\) operation that performs on exactly two operands, a two-terminal graph \(G_{1}\) and another two-terminal graph \(G_{2}\). The composed graph \(G_{s}=C_{s}(G_{1},G_{2})\) is another two-terminal graph that is the disjoint union of graphs \(G_{1}\) and \(G_{2}\) after unifying the destination node of \(G_{1}\) with the source node of \(G_{2}\). The source node of \(G_{s}\) is the source node of \(G_{1}\), and the destination node of \(G_{s}\) is the destination node of \(G_{2}\). Note that \(C_{s}(G_{1},G_{2})\
eq C_{s}(G_{2},G_{1})\). An example is demonstrated in Figure 1b.  
Now, we have everything set up to define series-parallel graphs.  
Definition 1: A series-parallel (SP) graph is a two-terminal graph that may be assembled from a set of connected pairs of nodes (source and destination nodes) with one edge using a specific order of the \(C_{p}\) and \(C_{s}\) operations.  
It is worth mentioning that all the nodes in an SP graph that are not the source node or the destination node must have a degree of at least 2. Furthermore, the SP graph is always a planar graph. Figure 1c shows an example of the SP graph. For the sake of simplicity, we will represent \(C_{s}(G_{1},G_{2})\) by \([G_{1},G_{2}]\), and \(C_{p}(G_{1},G_{2})\) by \([G_{1}\|G_{2}]\).