Computation of minimal rank and path cover number for certain graphs

By Francesco Barioli, Shaun M. Fallat, Leslie Hogben. 2004

104 citations recorded by the source corpus.

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 vertexdisjoint 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.

Subfields: Computational Theory and Mathematics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/413dead7b370208d1e1d1ad553a867f2349e9c5a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Geometry and Topology

Citations in the corpus

A variant on the graph parameters of Colin de Verdiere: Implications to the minimum rank of graphs (2005, background): “ξ(Cn) = 2, because M(Cn) = 2 (see for example [2, 3]) so ξ(Cn) 2, but Cn is not a disjoint union of paths so ξ(Cn) 2.”