Abstract

We show that equitable partitions, which are generalizations of graph symmetries, and Fourier transforms are fundamentally related. For a partition of a graph's vertices we define a Fourier similarity transform of the graph's adjacency matrix built from the matrices used to carryout discrete Fourier transformations. We show that the matrix (graph) decomposes into a number of smaller matrices (graphs) under this transformation if and only if the partition is an equitable partition. To extend this result to directed graphs we define two new types of equitable partitions, equitable receiving and equitable transmitting partitions, and show that if a partition of a directed graph is both, then the graph's adjacency matrix will similarly decomposes under this transformation. Since the transformation we use is a similarity transform the collective eigenvalues of the resulting matrices (graphs) is the same as the eigenvalues of the original untransformed matrix (graph).

Degree

MS

College and Department

Physical and Mathematical Sciences

Rights

https://lib.byu.edu/about/copyright/

Date Submitted

2021-03-31

Document Type

Thesis

Handle

http://hdl.lib.byu.edu/1877/etd11565

Keywords

Discrete Fourier Transform, graph, network, Fourier Similarity Transform, equitable partition, graph similarity

Language

english

Share

COinS