Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9498175 | Linear Algebra and its Applications | 2005 | 19 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
Authors
Francesco Barioli, Shaun Fallat, Leslie Hogben,