For a given undirected graph G, the maximum multiplicity of G is defined to be the largest multiplicity of an eigenvalue 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. We derive a formula for the path cover number of a vertex-sum of graphs, and use it to prove that the vertex-sum of so-called non-deficient graphs is non-deficient. For unicyclic graphs we provide a complete description of the path cover number and the maximum multiplicity (and hence the minimum rank), and we investigate the difference between path cover number and maximum multiplicity for a class of graphs referred to as block-cycle graphs.
Available at: http://works.bepress.com/leslie-hogben/60/
This is a manuscript of an article from Linear Algebra and its Applications 409 (2005): 13, doi:10.1016/j.laa.2004.09.014. Posted with permission.