Frames generated by graphs

Frames are the most natural generalization of orthonormal bases that allow the inclusion of redundant systems. In this article, we introduce the concept of frames generated by graphs in finite-dimensional spaces and study their properties. Let $G$ be a simple graph of $n$ vertices with Laplacian matrix $L$. We define the notions of $G(n,k)$-frames and $L_G(n,k)$-frames associated with the graph $G$. We obtain the family of dual frames of $L_G(n,k)$-frames and $G(n,k)$-frames. It is shown that non-regular graphs cannot generate tight frames. Then we establish a characterization of tight $G(n,k)$-frames in terms of the adjacency spectra of regular graphs. Besides, we provide a frame theoretic proof of an existing graph property. Finally, we show that one can use complete graphs to generate tight frames.