The Linear Complexity of a Graph

Authors

David L. Neel, Seattle University
Michael E. Orrison Jr., Harvey Mudd CollegeFollow

Document Type

Article

Department

Mathematics (HMC)

Publication Date

2-1-2006

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.

Comments

First published in The Electronic Journal of Combinatorics in vol. 13 (2006), published by the American Mathematical Society.

Rights Information

©2006 American Mathematical Society

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Recommended Citation

Neel, David L. and Orrison, Michael. "The linear complexity of a graph." Electronic Journal of Combinatorics 13 (2006), Research Paper 9. (electronic).