Connectivity matrix representation of graphs obtained by graph operations on complete bipartite graphs

Abstract

The connectivity matrix is an adjacency matrix with the property that each cell representing the connection between two nodes receives a value of one. Each cell that does not represent a direct connection gets a value of zero. Connectivity matrices are used in real-world applications such as finding the network tolerance of a network and brain connectivity. Our study mainly focuses on obtaining simple matrix representations for resulting graphs of finite summation and multiplication of 𝐾𝑚,𝑚. In our previous work, we have shown that the resulting graph of the product of 𝑛 copies of complete bipartite graphs (𝐾𝑚,𝑚) 𝑛 is also a complete bipartite graph, and the number of edges adjacent to each vertex is given by 2 𝑛−1 × 𝑚𝑛 and the summation of 𝑛 copies of 𝐾𝑚,𝑚 is not a complete bipartite graph, and the number of edges adjacent to one vertex is given by 𝑚(2𝑛 − 1). These resulting graphs are complicated. In our work, we have shown that the matrix representation of 𝐾𝑚,𝑚 is the 𝑚 × 𝑚 square matrix (𝑀𝑚) with all entries equal to 𝑀, where 𝑀 = [ 0 1 1 0 ] which is the matrix representation of 𝐾1,1. Matrix representation of (𝐾𝑚,𝑚) 𝑛 is a square matrix of order (2 𝑛−1𝑚𝑛 × 2 𝑛−1𝑚𝑛 ) with all entries equal to 𝑀 and this result is proved by mathematical induction where 𝑚 is the number of vertices in one partite set or degree of one vertex and 𝑛 represents the number of copies of 𝐾𝑚,𝑚. The matrix representation of the graph obtained by adding 𝑛 copies of 𝐾𝑚,𝑚 is, [ 𝑀𝑚 𝐽2𝑚 … 𝐽2𝑚 𝐽2𝑚 ⋱ ⋯ 𝐽2𝑚 ⋮ ⋮ ⋱ ⋮ 𝐽2𝑚 𝐽2𝑚 ⋯ 𝐽2𝑚 ], where 𝐽2𝑚 is the 2𝑚 × 2𝑚 matrix with all entries equal to 1. This result is also proved using mathematical induction. As an application, we plan to apply these theorems to prepare aeroplane routing plans.