Campus Units
Mathematics
Document Type
Article
Publication Version
Accepted Manuscript
Publication Date
11-2004
Journal or Book Title
Linear Algebra and its Applications
Volume
392
DOI
10.1016/j.laa.2004.06.019
Abstract
For a given undirected graph G, the minimum rank of G is defined to be the smallest possible rank over all real symmetric matrices A whose (i, j)th entry is non-zero whenever i ≠ j and {i, j} is an edge in G. The path cover number of G is the minimum number of vertex-disjoint paths occurring as induced subgraphs of G that cover all the vertices of G. For trees, the relationship between minimum rank and path cover number is completely understood. However, for non-trees only sporadic results are known. We derive formulae for the minimum rank and path cover number for graphs obtained from edge-sums, and formulae for minimum rank of vertex sums of graphs. In addition we examine previously identified special types of vertices and attempt to unify the theory behind them.
Rights
This manuscript version is made available under the CCBY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright Owner
Elsevier Inc.
Copyright Date
2004
Language
en
File Format
application/pdf
Recommended Citation
Barioli, Francesco; Fallat, Shaun; and Hogben, Leslie, "Computation of minimal rank and path cover number for certain graphs" (2004). Mathematics Publications. 76.
https://lib.dr.iastate.edu/math_pubs/76
Comments
This is a manuscript of an article from Linear Algebra and its Applications 392 (2004): 289, doi:10.1016/j.laa.2004.06.019. Posted with permission.