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
Hogben, Leslie
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Department
Mathematics
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.

Description
Keywords
Citation
DOI
Collections