Computation of minimal rank and path cover number for certain graphs
dc.contributor.author | Barioli, Francesco | |
dc.contributor.author | Fallat, Shaun | |
dc.contributor.author | Hogben, Leslie | |
dc.contributor.department | Mathematics | |
dc.date | 2020-06-19T01:55:17.000 | |
dc.date.accessioned | 2020-06-30T06:00:55Z | |
dc.date.available | 2020-06-30T06:00:55Z | |
dc.date.copyright | Thu Jan 01 00:00:00 UTC 2004 | |
dc.date.issued | 2004-11-15 | |
dc.description.abstract | <p>For a given undirected graph G, the minimum rank of G is defined to be the smallest possible rank 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. For trees, the relationship between minimum rank and path cover number is completely understood. However, for non-trees only sporadic results are known. We derive formulae for the minimum rank and path cover number for graphs obtained from edge-sums, and formulae for minimum rank of vertex sums of graphs. In addition we examine previously identified special types of vertices and attempt to unify the theory behind them.</p> | |
dc.description.comments | <p>This is a manuscript of an article published as Barioli, Francesco, Shaun Fallat, and Leslie Hogben. "Computation of minimal rank and path cover number for certain graphs." 392 <em>Linear Algebra and its Applications</em> (2004): 289-303. DOI:<a href="http://dx.doi.org/10.1016/j.laa.2004.06.019" target="_blank">10.1016/j.laa.2004.06.019</a>. Posted with permission.</p> | |
dc.format.mimetype | application/pdf | |
dc.identifier | archive/lib.dr.iastate.edu/math_pubs/76/ | |
dc.identifier.articleid | 1091 | |
dc.identifier.contextkey | 9891649 | |
dc.identifier.s3bucket | isulib-bepress-aws-west | |
dc.identifier.submissionpath | math_pubs/76 | |
dc.identifier.uri | https://dr.lib.iastate.edu/handle/20.500.12876/54674 | |
dc.language.iso | en | |
dc.source.bitstream | archive/lib.dr.iastate.edu/math_pubs/76/2004_Hogben_ComputationMinimal.pdf|||Sat Jan 15 01:50:59 UTC 2022 | |
dc.source.uri | 10.1016/j.laa.2004.06.019 | |
dc.subject.disciplines | Algebra | |
dc.subject.disciplines | Discrete Mathematics and Combinatorics | |
dc.subject.keywords | Graphs | |
dc.subject.keywords | Minimum rank | |
dc.subject.keywords | Path cover number | |
dc.subject.keywords | Symmetric matrices | |
dc.subject.keywords | Vertex sum | |
dc.subject.keywords | Edge sum | |
dc.title | Computation of minimal rank and path cover number for certain 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 |
File
Original bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- 2004_Hogben_ComputationMinimal.pdf
- Size:
- 234.03 KB
- Format:
- Adobe Portable Document Format
- Description: