Eigenvalue Interlacing of Bipartite Graphs and Construction of Expander Code using Vertex-split of a Bipartite Graph

Authors

  • Machasri Manickam Division of Mathematics, School of Advanced Sciences, Vellore Institute of Technology, Chennai, Tamilnadu, India
  • Kalyani Desikan Department of Mathematics, School of Advanced Sciences, Vellore Institute of Technology, Chennai, India

DOI:

https://doi.org/10.29020/nybg.ejpam.v17i2.5057

Keywords:

expander code, vertex-split, second largest eigenvalue, bipartite graph, quotient matrix

Abstract

The second largest eigenvalue of a graph is an important algebraic parameter which is related with the expansion, connectivity and randomness properties of a graph. Expanders are highly connected sparse graphs. In coding theory, Expander codes are Error Correcting codes made up of bipartite expander graphs. In this paper,  first we prove the interlacing of the eigenvalues of the adjacency matrix of the bipartite graph with the eigenvalues of the bipartite quotient matrices of the corresponding graph matrices. Then we obtain bounds for the second largest and second smallest eigenvalues. Since the graph is bipartite, the results for Laplacian will also hold for Signless Laplacian matrix. We then introduce a new method called vertex-split of a bipartite graph to construct asymptotically good expander codes with expansion factor D/2 < alpha  < D and epsilon < 1/2 and prove a condition for the vertex-split of a bipartite graph to be k-connected with respect to the second largest eigenvalue: Further, we prove that the vertex-split of G is a bipartite expander. Finally, we construct an asymptotically good expander code whose factor graph is a graph obtained by the vertex-split of a bipartite graph.

Downloads

Published

2024-04-30

Issue

Section

Nonlinear Analysis

How to Cite

Eigenvalue Interlacing of Bipartite Graphs and Construction of Expander Code using Vertex-split of a Bipartite Graph. (2024). European Journal of Pure and Applied Mathematics, 17(2), 772-789. https://doi.org/10.29020/nybg.ejpam.v17i2.5057