Signal processing on graphs finds applications in many areas. Motivated by recent developments, this paper studies the concept of spectrum folding (aliasing) for graph signals under the downsample-then-upsample operation. In this development, we use a special eigenvector structure that is unique to the adjacency matrix of M-block cyclic matrices. We then introduce M-channel maximally decimated filter banks. Manipulating the characteristics of the aliasing effect, we construct polynomial filter banks with perfect reconstruction property. Later we describe how we can remove the eigenvector condition by using a generalized decimator. In this study graphs are assumed to be general with a possibly non-symmetric and complex adjacency matrix.