# Vertex Labeling and Routing for Farey-Type Symmetrically-Structured Graphs
## 5 Routing of \(GF(t,k)\) and \(EF(t,k)\)
The vertices of \(F(b_{1}-b_{3})\) and \(F(b_{2}-b_{3})\) can be divided into six parts similarly: \(V_{\alpha}^{x}(t)\), \(V_{\alpha}^{xy}(t)\), \(V_{\alpha}^{y}(t)\) and \(V_{\beta}^{x}(t)\), \(V_{\beta}^{xy}(t)\), \(V_{\beta}^{y}(t)\), by the distance between \(a.b_{1}.c_{1}.d_{1}\) or \(a.b_{2}.c_{2}.d_{2}\) to initial vertices \(X\) (i.e., \(a.b_{3}.c_{3}.d_{3}\)) and \(Y\) (i.e., \(a. (b_{3}+1).c_{4}.d_{4}\)), in which case then the shortest paths between \(a.b_{1}.c_{1}.d_{1}\) and \(a.b_{2}.c_{2}.d_{2}\) go via \(a.b_{3}.c_{3}.d_{3}\), if  
(a) \(a.b_{1}.c_{1}\in V_{\alpha}^{x}(t)\) and \(a.b_{2}.c_{2}\in V_{\beta}^{xy}(t)\),  
(b) \(a.b_{1}.c_{1}\in V_{\alpha}^{x}(t)\) and \(a.b_{2}.c_{2}\in V_{\beta}^{xy}(t)\),  
(c) or \(a.b_{1}.c_{1}\in V_{\alpha}^{xy}(t)\) and \(a.b_{2}.c_{2}\in V_{\beta}^{x}(t)\). The shortest paths go through \(a.b_{3}.c_{3}.d_{3}\) and \(a. (b_{3}+1).c_{4}.d_{4}\), if  
(a) \(a.b_{1}.c_{1}\in V_{\alpha}^{x}(t)\) and \(a.b_{2}.c_{2}\in V_{\beta}^{y}(t)\),  
(b) or \(a.b_{1}.c_{1}\in V_{\alpha}^{xy}(t)\) and \(a.b_{2}.c_{2}\in V_{\beta}^{xy}(t)\),  
(c) \(a.b_{1}.c_{1}\in V_{\alpha}^{y}(t)\) and \(a.b_{2}.c_{2}\in V_{\beta}^{x}(t)\). The shortest paths pass \(a. (b_{3}+1).c_{4}.d_{4}\), if  
(a) \(a.b_{1}.c_{1}\in V_{\alpha}^{xy}(t)\) and \(a.b_{2}.c_{2}\in V_{\beta}^{y}(t)\),  
(b) \(a.b_{1}.c_{1}\in V_{\alpha}^{y}(t)\) and \(a.b_{2}.c_{2}\in V_{\beta}^{y}(t)\),  
(c) or \(a.b_{1}.c_{1}\in V_{\alpha}^{y}(t)\) and \(a.b_{2}.c_{2}\in V_{\beta}^{y}(t)\). \(\square\)  
**Property 13. **_(The characteristic of shortest paths when two vertices are in same slice) If \(a.b_{1}.c_{1}.d_{1}\) and \(a.b_{2}.c_{2}.d_{2}\) are in the same slice of a petal or subpetal of same group, the shortest paths between them are determined by Property 5, as they have been projected onto a Farey graph._  
**Proof. ** If we obtained only one common neighbor vertex, labeled with \(a.b_{3}.c_{3}.d_{3}\), of vertices \(a.b_{1}.c_{1}.d_{1}\) and \(a.b_{2}.c_{2}.d_{2}\) at the same step, then \(a.b_{1}.c_{1}.d_{1}\) and \(a.b_{2}.c_{2}.d_{2}\) are located in same slice. Assuming \(b_{1}\geq b_{2}\), the projected Farey graph is \(F(b_{1}-b_{3}-1)\) with a hub vertex \(a.b_{1}.c_{1}.d_{1}\), in which case all the shortest paths are located in \(F(b_{1}-b_{3}-1)\). So that all the shortest paths can be decided by Property 5. \(\square\)  
The detailed shortest routing algorithm in GFG/EFG is described as follows. **Property 14. **_(The shortest paths routing algorithm in GFG/EFG)_  
_1. Given any two vertices \(a_{1}.b_{1}.c_{1}.d_{1}\) and \(a_{2}.b_{2}.c_{2}.d_{2}\), insert \(a_{1}.b_{1}.c_{1}.d_{1}\) and \(a_{2}.b_{2}.c_{2}.d_{2}\) into the labels set of the shortest paths (\(LSSP_{m}(h)\)), \(LSSP_{m}(0)=\varnothing\)._  
_2. If \(a_{1}\
eq a_{2}\), and both \(a_{1}.b_{1}.c_{1}.d_{1}\) and \(a_{2}.b_{2}.c_{2}.d_{2}\) are not initial vertices, then this is exactly the condition of two vertices being in different groups. Three initial vertices \(\{0,1,2\}/\left\{a_{1},a_{2}\right\}\), \(a_{1}\) and \(a_{2}\) are ascertained as being on the shortest paths or not by property 11.__If only one common neighbor is obtained at the same time, then a.b.\({}_{1}\).\({}_{1}\).\({}_{1}\).\({}_{1}\) and a.\({}_{2}\).\({}_{2}\).\({}_{2}\).\({}_{2}\) are located in same slice. The shortest paths are projected into a Farey graph, and then all the shortest paths are derived by Property 5._  
**Remark 6**: _The expanded deterministic Apollonian networks, denoted by \(A(d,t)\), are the generalization of Apollonian networks, being simultaneously small-world, scale-free and highly clustered. The label-based routing protocol for it is deduced in [35]. \(A(d,t)\) (\(d\geq 1\) and \(t\geq 0\)) are constructed as follows. \(A(d,0)\) is a complete graph \(K_{d+2}\) (or \(d+1\)-clique). \(A(d,t)\) (\(t\geq 1\)) is obtained from \(A(d,t-1)\) by adding one new node and connecting it to all the nodes of each existing subgraph of \(A(d,t-1)\) that is isomorphic to a (\(d+1\))-clique and created at step \(t-1\).