# Vertex Labeling and Routing for Farey-Type Symmetrically-Structured Graphs
## 2 Generation of Farey-Type Graphs  
GFG and EFG are generalized from FG; we present the definitions of the three in turn.  
**Definition 1**.: _(Generation of FG) Farey graph \(F(t)=(V(t),E(t))\) is constructed as follows (see Figure 1), in which the iteration step \(t\geq 0\), with vertex set \(V(t)\) and edge set \(E(t)\)[6]:_  
* \(F(0)\) _has two vertices and an edge._
* _For_ \(t\geq 1\)_,_ \(F(t)\) _is obtained from_ \(F(t-1)\) _by adding a new vertex to every edge which is introduced at step_ \(t-1\) _in_ \(F(t-1)\)_, then to linking the new vertex to the two vertices of that edge._  
Figure 1: The Farey graphs \(F(t)\). (From left to right, \(F(0)\), \(F(1)\), \(F(2)\) and \(F(3)\)).  
**Remark 1**.: _The number of vertices added at step \(t\) is \(\Delta n_{t}=2^{t-1}\), so that the order of FG is \(|V(t)|=2^{t}+1\) and the size is \(|E(t)|=2^{t+1}+1\), respectively. The cumulative degree distribution follows an exponential distribution \(P_{cum}(\delta)=2^{-\frac{\delta}{2}}\), and the degree correlation \(k_{m}(\delta)\) is approximately a linear function of \(\delta\)[6; 7]._  
_All the vertices in \(F(t)\) are divided into three groups by their distances to two initial vertices \(X\) and \(Y\): \(V^{x}(t)\), \(V^{xy}(t)\) and \(V^{y}(t)\). The nodes in \(V^{y}(t)\) (including \(Y\)) have shorter distances to \(Y\) than to \(X\), while \(V^{x}(t)\) (including \(X\)) have shorter distances to \(X\), and in \(V^{xy}(t)\) the distances are equal. That is to say, \(V(t)=V^{x}(t)\cup V^{xy}(t)\cup V^{y}(t)\). As \(X\) and \(Y\) are neighbors, the difference in distances above are 0 or 1. If two copies of \(F(t)\) are named as \(F_{1}(t)\) and \(F_{2}(t)\), the initial vertices are \(X_{1}\), \(Y_{1}\) and \(X_{2}\), \(Y_{2}\), then \(F(t+1)\) is generated as shown in Figure 2._  
**Definition 2**.: _(Generation of GFG) \(GF(t,k)\) is deduced by the rules (see Figure 3):_  
* _For_ \(t=0\)_,_ \(GF(0,k)\) _is composed of three initial vertices which are linked to each other._
* _For_ \(t\geq 1\)_,_ \(GF(t,k)\) _is constructed from_ \(GF(t-1,k)\) _by adding_ \(k\) _new vertices to every edge introduced at step_ \(t-1\)_, then linking the_ \(k\) _new vertices to the two end vertices._  
**Remark 2**.: \(GF(t,1)\) _is exactly the graphs created by edge iterations [8]. It is just the evolving graphs with geographical attachment preference [9]. GFG can also be treated as a flower, which has \(3\times k\) identical petals, denoting as \(P_{i}(t)\), \(i=1,2,\ldots,3\times k\). All petals are rooted from two initial vertices, as a GFG is made up of three groups, so that each group contains \(k\) identical petals._  
Figure 3: \(Cont\).  
Figure 2: The construction of \(F(t+1)\).  
**Definition 3**.: _(Generation of EFG) The construction of \(EF(t,k)\) is shown as below:_  
* _For_ \(t=0\)_,_ \(EF(0,k)\) _holds three vertices that are linked to each other._
* _For_ \(t\geq 1\)_,_ \(EF(t,k)\) _is constructed from_ \(EF(t-1,k)\) _by adding_ \(k\) _new vertices to every edge linked at step_ \(t-1\) _and three initial edges added at_ \(t=0\)_, then linking the_ \(k\) _new vertices to the two end vertices (see Figure_ 4_)._  
Figure 4: The extended Farey graphs. (**a**) \(EF(t,k)\) at steps \(t=0\), \(1\) and \(2\) when \(k=1\); (**b**) \(EF(t,k)\) at steps \(t=0\), \(1\) and \(2\) when \(k=2\).  
Figure 3: The generalization of Farey graphs. (**a**) \(GF(t,k)\) at steps \(t=0\), \(1\) and \(2\) when \(k=1\); (**b**) \(GF(t,k)\) at steps \(t=0\), \(1\) and \(2\) when \(k=2\).  
**Remark 3**.: _The generation method of EFG is slightly different from GFG, which lies in the three initial edges, not only the edges merged at step \(t-1\), but as active edges that can generate new vertices. EFG has \(3\times t\times k\) petals, named \(P_{i}(t_{j})\), \(i=1,2,\ldots,3\times k\) and \(t_{j}=0,1,\ldots,t\); a GFG is therefore just part of an equivalent EFG._