# Vertex Labeling and Routing for Farey-Type Symmetrically-Structured Graphs
## 3 Labeling and Routing of \(F(t)\)  
The labeling and routing protocol of GFG and EFG are extended from FG; the label-based routing algorithm was originally derived in [33], but we redefine it here for completeness and clarity. In order to save space, we do not repeat the proofs of these properties in this section. **Definition 4**. : _Labeling any vertex in FG as follow (see Figure 5):_  
* _Label two initial vertices as_ \(0.1\) _and_ \(0.0\) _when_ \(t=0\)_._
* _When_ \(t\geq 1\)_, the new vertices added at step_ \(t\) _are marked with labels from_ \(t.1\) _to_ \(t.2^{t-1}\) _in a clockwise direction._  
Supposing any two vertices are labeled with \(t_{i}.k\) and \(t_{j}.l\), and \(t_{i}\geq t_{j}\). Then the mother vertex of \(t_{i}.k\) added to the graph at step \(t_{i}-1\). Two vertices with same mother are brothers. The father is added to the graph at step \(t_{i}-2\) or earlier. The following relationships between different vertices, are extracted with the help of their labels. **Property 1**. : _(The family of \(t_{i}.k\))_  
_Two children of_ \(t_{i}.k\) _are_ \((t_{i}+1). (2k-1)\) _and_ \((t_{i}+1).2k\) _when_ \(t_{i}\geq 1\)_._  
_When_ \(t_{i}\geq 2\)_, The brother of_ \(t_{i}.k\) _is_ \(t_{i}. (k+1)\) _(when_ \(k\) _is odd) or_ \(t_{i}. (k-1)\) _(when_ \(k\) _is even)._  
_When_ \(t_{i}\geq 2\)_,_ \(t_{i}.k\) _and its parents shapes a triangle. The mother is_ \((t_{i}-1).\left\lfloor\frac{k}{2}\right\rfloor\) _and the father is_ \((t_{i}-1).\left\lfloor\frac{k-rem(k,2)}{2^{i}}\right\rfloor\) _(in which_ \(rem(k,2)\) _is the remainder of_ \(k\) _divided by_ \(2\)_,_ \(\left\lfloor x\right\rfloor=floor(x)\) _is a function rounding the real number_ \(x\) _down towards the nearest integer. The integer_ \(l(\geq 2)\) _is the number of the continuous zeros from right to left in the binary sequence created by converting the value of_ \(k-rem(k,2)\) _to base 2, plus one, that is,_ \(l=\) _Function(k-rem (k,2))._  
_If_ \(t_{i}\geq t_{j}\)_, the_ \((t_{i}-t_{j})\)_th generation of maternal ancestor of_ \(t_{i}.k\) _is_ \(t_{j}.\left\lfloor\frac{k}{2^{i-t_{j}}}\right\rfloor\)_._  
**Property 2**. : _(The neighbors of_ \(t_{i}.k\)  
Figure 5: Labels of all vertices in \(F(5)\). _When \(t_{i}=0\), the neighbors of \(0.0\) is \(\{x.1\}\), \(x\in\{0,1,2,\ldots,t\}\), and the neighbors of \(0.1\) are \(\left\{0.0,x.2^{x-1}\right\}\), \(x\in\{1,2,\ldots,t\}\)._  
_When \(t_{i}=1\), the neighbors of \(1.1\) are \(\left\{0.0,0.1,(1+x).2^{x-1}(2k-1),(1+x). [2^{x-1}(2k-1)+1]\right\}\), \(x\in\{0,1,2,\ldots,t\}\)._  
_When \(t_{i}\geq 2\), the neighbors of \(t_{i}.k\) are \(\{(t_{i}-l).\ \left\lfloor\frac{k-rem(k,2)}{2^{l}}\right\rfloor,(t_{i}-1). \left\lfloor\frac{k}{2}\right\rfloor,(t_{i}+x).2^{x-1}(2k-1),\)\((t_{i}+x). [2^{x-1}(2k-1)+1]\}\), \(x\in\{1,2,\ldots,\ t-t_{i}\}\)._  
**Property 3**. : _When two vertices are located in different subgraphs \(F_{1}(t-1)\) and \(F_{2}(t-1)\) of \(F(t)\), the hub \(X\) of \(F(t)\) is on the shortest paths, if_  
_(1) \(t_{i}.k\in V_{2}^{x}(t-1)\) and \(t_{j}.l\in V_{1}^{y}(t-1)/\{Y_{1}\}\),_  
_(2) \(or\ t_{i}.k\in V_{1}^{x}(t-1)\) and \(t_{j}.l\in V_{2}^{y}(t-1)/\{Y_{2}\}\),_  
_(3) \(or\ t_{i}.k\in V_{2}^{x}(t-1)\cup V_{2}^{xy}(t-1)\) and \(t_{j}.l\in V_{1}^{x}(t-1)\cup V_{1}^{xy}(t-1)\),_  
_(4) \(t_{i}.k\in V_{1}^{x}(t-1)\cup V_{1}^{xy}(t-1)\) and \(t_{j}.l\in V_{2}^{x}(t-1)\cup V_{2}^{xy}(t-1)\). Two initial vertices \(Y_{1}\) and \(Y_{2}\) of \(F(t)\) are located on the shortest paths if_  
_(1) \(t_{i}.k\in V_{2}^{y}(t-1)\) and \(t_{j}.l\in V_{1}^{y}(t-1)\),_  
_(2) \(or\ t_{i}.k\in V_{1}^{y}(t-1)\) and \(t_{j}.l\in V_{2}^{y}(t-1)\)._  
_Vertices \(X\), \(Y_{1}\) and \(Y_{2}\) lie on the shortest paths simultaneously if_  
_(1) \(t_{i}.k\in V_{2}^{y}(t-1)\) and \(t_{j}.l\in V_{1}^{xy}(t-1)\),_  
_(a) \(or\ t_{i}.k\in V_{1}^{y}(t-1)\) and \(t_{j}.l\in V_{2}^{xy}(t-1)\)._  
**Property 4**. : _All the shortest paths between any pair of vertices are located a minimum common subgraph (MCSG) denoted as \(F^{mcsg}(t_{min})\).