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.
©2006 American Mathematical Society
Neel, David L. and Orrison, Michael. "The linear complexity of a graph." Electronic Journal of Combinatorics 13 (2006), Research Paper 9. (electronic).