#### Campus Units

Mathematics

#### Document Type

Article

#### Publication Version

Accepted Manuscript

#### Publication Date

11-2005

#### Journal or Book Title

Linear Algebra and its Applications

#### Volume

409

#### DOI

10.1016/j.laa.2004.09.014

#### Abstract

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.

#### 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, "On the difference between the maximum multiplicity and path cover number for tree-like graphs" (2005). *Mathematics Publications*. 78.

https://lib.dr.iastate.edu/math_pubs/78

## Comments

This is a manuscript of an article from

Linear Algebra and its Applications409 (2005): 13, doi:10.1016/j.laa.2004.09.014. Posted with permission.