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.

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.

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.

Language

en

File Format

application/pdf

Published Version

Share

COinS