Powers of the adjacency matrix and the walk matrix

Abstract

The aim of this article is to identify and prove various relations between powers of adjacency matrices of graphs and various invariant properties of graphs, in particular distance, diameter and bipartiteness. A relation between the walk matrix of a graph and a subset of the cigenvectors of the graph will also be illustrated. A number of Mathematica procedures are also provided which implement the results described. Note that the procedures are only illustrative; issues of algorithmic efficiency are largely ignored.

Unless specified, all graphs are assumed to be simple and connected, that is, there is at most one edge between each pair of vertices, there are no loops, and there is at least one path between every two vertices. The adjacency matrix A or A(G) of a graph G having vertex set V = V(G) = {1, ... , n} is an n x n symmetric: matrix aij such that aij = 1 if vertices i and j are adjacent and 0 otherwise.