Skip to main content
Article
On the difference between the maximum multiplicity and path cover number for tree-like graphs
Linear Algebra and its Applications
  • Francesco Barioli, Carleton University
  • Shaun Fallat, University of Regina
  • Leslie Hogben, Iowa State University
Document Type
Article
Publication Version
Accepted Manuscript
Publication Date
11-1-2005
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.

Comments

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.

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
Citation Information
Francesco Barioli, Shaun Fallat and Leslie Hogben. "On the difference between the maximum multiplicity and path cover number for tree-like graphs" Linear Algebra and its Applications Vol. 409 (2005)
Available at: http://works.bepress.com/leslie-hogben/60/