# On Orthogonal Double Covers and Decompositions of Complete Bipartite Graphs by Caterpillar Graphs
## 1 Introduction
: _Figure 1 illustrates the path graph \(P_{4}\) and how the graphs \(C_{4}(2,2,1,1)\) and \(C_{4}(1,3,2,2)\) can be obtained from \(P_{4}\)._  
The following definition has been proposed in [34]. Let \(H\) be a certain graph, the graph \(G\)-Path denoted by \(\mathbb{P}_{m+1}(G)\), is a path of a set of vertices \(\mathbb{V}=\{V_{i}:0\leq i\leq m\}\) and a set of edges \(\mathbb{E}=\{E_{i}:0\leq i\leq m-1\}\) if and only if there exists the following two bijective mappings:  
1. \(\phi\): \(\mathbb{E}\rightarrow\mathcal{H}\) defined by \(\phi(E_{i})=H_{i}\), where \(\mathcal{H}=\{H_{0},H_{1},\ldots,H_{m-1}\}\) is a collection of \(m\) graphs; each one is isomorphic to the graph \(G\). 2. \(\psi:\ \mathbb{V}\rightarrow\mathcal{A}\) defined by \(\psi(V_{i})=X_{i}\), where \(\mathcal{A}=\{X_{i}:0\leq i\leq m:\cap_{i}X_{i}=\varphi\}\) is a class of disjoint sets of vertices. \begin{table}
\begin{tabular}{c c} \hline \hline  & **Nomenclature** \\ \hline \(K_{x,y}\) & A complete bipartite graph with independent sets of sizes \(x\) and \(y\). \\ gcd & The greatest common divisor. \\ \(mG\) & \(m\) disjoint copies of \(G\). \\ \(G\cup H\) & The disjoint union of \(G\) and \(H\). \\ \(S_{x}\) & A star with \(x\) edges on \(x+1\) vertices. \\ \(P_{x}\) & A path with \(x\) vertices. \\ \(K_{1}\) & An isolated vertex. \\ \(C(N;s_{1},s_{2},s_{3})\) & Three-dimensional circulant graph. \(N\)–number of nodes; \(s_{1},s_{2},s_{3}\)–generators. \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Designations used in the paper. Similarly, the caterpillar graph definition can be shown by replacing the path graph with the caterpillar graph in the previous definition. The caterpillar graph corresponding to the caterpillar \(C_{l}(w_{1},w_{2},\ldots,w_{l})\) will be denoted by \(\mathbb{C}_{l}^{w_{1},w_{2},\ldots,w_{l}}(G)\). In the main results section, several examples for the caterpillar graph are presented. There are extensive studies in the literature for the \(ODC\) of complete bipartite graphs such as the technique for constructing the \(ODC\)s of \(K_{x,x}\) by copies of a graph, which is called the one-edge algorithm [35]. Additionally, there are many studies for constructing the \(ODC\)s of \(K_{x,x}\) by special graphs such as the union of a cycle and a star, a special class of six caterpillars [36], and the disjoint union of complete bipartite graphs. Several results of the \(ODC\)s of complete bipartite graphs can be generalized to mutually orthogonal graph squares that have many applications in design theory, graph-orthogonal arrays, and authentication codes [37]. Additionally, the techniques of constructing the \(ODC\)s are considered a tool for graph labeling called orthogonal labeling, which have many applications (for example, see [38]). Figure 1: The graphs \(P_{u}\), \(C_{4}(2,2,1,1)\) and \(C_{4}(1,3,2,2)\). Figure 2: \(\mathbb{P}_{6}(K_{1,3})\), the path of six sets of vertices and five edges of \(K_{1,3}\). Motivated by all the previous results and the important applications of caterpillar graphs [4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21], in this paper, we aim to decompose giant graphs for the special type of networks (complete bipartite graphs) by joint and disjoint copies of new generally symmetric graphs called caterpillar graphs. The design of the study can be explained as follows: large complete bipartite networks and a symmetric starter vector method are applied to represent caterpillar graphs, which can be generated and used in many applications such as the analysis and decomposition of the large complete bipartite graphs (networks). The caterpillar graph used to decompose the complete bipartite graph are: the stars-caterpillar graph; the disjoint copies of cycles-caterpillars; the complete bipartite caterpillar graphs; and the disjoint copies of caterpillar paths. Additionally, we decompose the complete bipartite giant graph by the complete bipartite subgraphs and by the disjoint copies of complete bipartite subgraphs using general symmetric starter vectors.