Frames generated by graphs

Abstract

Frames generalize orthonormal bases by allowing redundancy, which ensures stability and resilience in applications ranging from signal processing to data transmission. In this article, we introduce a new class of finite frames constructed from graphs and called them frames generated by graphs. Given a simple graph G with Laplacian matrix L(G), we define the notions of G(n, k)-frames and LG(n,k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_G(n, k)$$\end{document}-frames, and establish their fundamental properties. We demonstrate that the frame operator and the dual frame of a G(n, k)-frame and an LG(n,k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_G(n,k)$$\end{document}-frame admit simplified forms. It is shown that tight frames generated by graphs are uniform frames, and after normalization, biangular frames. We provide characterization of frames generated by graphs to be tight frame in terms of adjacency spectra of graphs. Furthermore, we prove that frames generated by complete graphs are tight frames.