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

dc.contributor.author Barioli, Francesco
dc.contributor.author Fallat, Shaun
dc.contributor.author Hogben, Leslie
dc.contributor.author Hogben, Leslie
dc.contributor.department Mathematics
dc.date 2018-02-18T06:09:11.000
dc.date.accessioned 2020-06-30T06:00:56Z
dc.date.available 2020-06-30T06:00:56Z
dc.date.copyright Thu Jan 01 00:00:00 UTC 2004
dc.date.issued 2005-11-01
dc.description.abstract <p>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.</p>
dc.description.comments <p>This is a manuscript of an article from <em>Linear Algebra and its Applications </em>409 (2005): 13, doi:<a href="http://dx.doi.org/10.1016/j.laa.2004.09.014" target="_blank">10.1016/j.laa.2004.09.014</a>. Posted with permission.</p>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/math_pubs/78/
dc.identifier.articleid 1089
dc.identifier.contextkey 9890998
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath math_pubs/78
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/54676
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/math_pubs/78/2005_Hogben_DifferenceMaximum.pdf|||Sat Jan 15 01:54:13 UTC 2022
dc.source.uri 10.1016/j.laa.2004.09.014
dc.subject.disciplines Algebra
dc.subject.disciplines Discrete Mathematics and Combinatorics
dc.subject.keywords Graphs
dc.subject.keywords Minimum rank
dc.subject.keywords Maximum multiplicity
dc.subject.keywords Path cover number
dc.subject.keywords Vertex-sums
dc.subject.keywords Unicyclic graphs
dc.subject.keywords Block-cycle graphs
dc.title On the difference between the maximum multiplicity and path cover number for tree-like graphs
dc.type article
dc.type.genre article
dspace.entity.type Publication
relation.isAuthorOfPublication 0131698a-00df-41ad-8919-35fb630b282b
relation.isOrgUnitOfPublication 82295b2b-0f85-4929-9659-075c93e82c48
Original bundle
Now showing 1 - 1 of 1
242.57 KB
Adobe Portable Document Format