On pseudo walk matrices

Abstract

A pseudo walk matrix associated with a graph G having adjacency matrix A is a matrix with columns v, Av, A2 v, …, Ar−1 v (for a specific r) where the Gram matrix of these columns contains particular walk enumerations in G. For any subset S of the Cartesian product of the vertex set V(G) with itself, we consider the total number of walks N0(S), N1(S), N2(S), … of length 0, 1, 2, … in G that start from vertex i and end at vertex j for all (i, j) ∈ S. We present a method that, given such a set S, produces a walk vector v (with possibly complex entries) such that the Gram matrix of the columns of the pseudo walk matrix resulting from this walk vector is the Hankel matrix whose skew diagonals contain the values N0(S), …, N2r−2(S). Various results on such pseudo walk matrices are derived, particularly on closed pseudo walk matrices whose set S contains only the pairs (v, v) for all v ∈ V(G). Moreover, a result akin to the classic Harary-Sachs coefficient theorem in chemical graph theory that computes any coefficient of the characteristic polynomial of the companion matrix of a pseudo walk matrix is conveyed.