The linear complexity of a graph

MaRDI QIDQ813437zbMATH OpenFDO

Authors David L. Neel, Michael E. Orrison

Publication date 9 February 2006

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/125526, http://www.emis.de/journals/EJC/Volume_13/Abstracts/v13i1r9.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

adjacency matrices

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Review text

Summary: 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.

Recommendations

• The linear complexity of a graph
• On Graph Complexity
• Graphs of linear operators
• Graph complexity
• Complexity metric and structural measure on the class of deterministic matrices

Cited in

(13)

• A bound for the complexity of a simple graph
• The complexity of finite graphs
• On the likelihood of forests
• On measuring the complexity of networks: Kolmogorov complexity versus entropy
• Consistency matters: revisiting the structural complexity for supply chain networks
• The linear complexity of a graph
• Complexity metric and structural measure on the class of deterministic matrices
• MAX-plus objects to study the complexity of graphs
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Kolmogorov's complexity for positive definite matrices
• Comparison between the complexity of a function and the complexity of its graph
• The complexity of growing a graph
• Graphs of linear operators

This page was built for publication: The linear complexity of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q813437)