Electronic Journal of Linear Algebra · 2005 · 44 citations · 10 references
Natural SciencesComputer ScienceMathematicsCombinatoricsEdge ComputingOptimizationDirected Acyclic GraphsGraph AlgorithmsGraph TheoryGraph-based LearningMatrix StructureAlgebraic Graph Theory
For a given undirected graph G, the minimum rankof G is defined to be the smallestpossible rankover all real symmetric matrices A whose (i, j)th entry is nonzero whenever i≠ j and{i, j} is an edge in G. Building upon recent workinvolving maximal coranks (or nullities) of certainsymmetric matrices associated with a graph, a new parameter ξ is introduced that is based on the corankof a different but related class of symmetric matrices. For this new parameter some properties analogous to the ones possessed by the existing parameters are verified. In addition, an attempt is made to apply these properties associated with ξ to learn more about the minimum rankof graphs– the original motivation.
10