On the difference between the maximum multiplicity and path cover number for tree-like graphs

Date
2005-11-01
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 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.

Description

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.

Keywords
Graphs, Minimum rank, Maximum multiplicity, Path cover number, Vertex-sums, Unicyclic graphs, Block-cycle graphs
Citation
DOI
Collections