Computation of minimal rank and path cover number for certain graphs

Date
2004-11-15
Authors
Barioli, Francesco
Fallat, Shaun
Hogben, Leslie
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
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.

Description

This is a manuscript of an article published as Barioli, Francesco, Shaun Fallat, and Leslie Hogben. "Computation of minimal rank and path cover number for certain graphs." 392 Linear Algebra and its Applications (2004): 289-303. DOI:10.1016/j.laa.2004.06.019. Posted with permission.

Keywords
Graphs, Minimum rank, Path cover number, Symmetric matrices, Vertex sum, Edge sum
Citation
DOI
Collections