2019/10/31 by Fenjin Liu, Liu, Fenjin, Johannes Siemons +1 · 1 citation
Computer Science · Mathematics · #05C50 #05C75 #05E10 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #G.2.2 #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.1911.00062
openalex publication_date 2019/10/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a graph with vertex set V=\v1,…,vn\ and adjacency matrix A. For a subset S of V let \e=(x1, …, xn)\tt T be the characteristic vector of S, that is, xℓ=1 if vℓ∈ S and xℓ=0 otherwise. Then the n× n matrix WS:=[\rm e, A\rm e, A2\rm e,…,An-1\rm e] is the \it walk matrix of G for S. This name relates to the fact that in WS the k\rm th entry in the row corresponding to vℓ is the number of walks of length k-1 from vℓ to some vertex in S. Since A is symmetric the characteristic vector of S can be written uniquely as a sum of eigenvectors of A. In particular, we may enumerate the distinct eigenvalues μ1,…, μs of A so that \rm SD(S) : \eamp;=amp;\e1+\e2+…+\er where r≤ s and \ei is an eigenvector of A of μi for all 1≤ i≤ r. We refer to (\refSSA) as the \it spectral decomposition of S, or more properly, of its characteristic vector. The key result of this paper is that the walk matrix WS determines the spectral decomposition of S and \it vice versa. This holds for any non-empty set S of vertices of the graph and explicit algorithms which establish this correspondence are given. In particular, we show that the number of distinct eigenvectors that appear in (\refSSA) is equal to the rank of WS. Several theorems can be derived from this result. We show that WS determines the adjacency matrix of G if WS has rank ≥ n-1. This theorem is best possible as there are examples of pairs of graphs with the same walk matrix of rank n-2 but with different adjacency matrices.