The Linear Complexity of a Graph

  • David L. Neel
  • Michael E. Orrison
DOI: https://doi.org/10.37236/1035

Abstract

The linear complexity of a matrix is a measure of the number of additions, subtractions, and scalar multiplications required to multiply that matrix and an arbitrary vector. In this paper, we define the linear complexity of a graph to be the linear complexity of any one of its associated adjacency matrices. We then compute or give upper bounds for the linear complexity of several classes of graphs.

Published
2006-02-01
Issue
Volume 13 (2006)
Article Number
R9