{"id":{"repo_id":"byu","oai_identifier":"oai:scholarsarchive.byu.edu:etd-2109"},"canonical_url":"https://search.dev.ndltd.org/etd/byu/oai:scholarsarchive.byu.edu:etd-2109","repository":{"repo_id":"byu","name":"Brigham Young University","base_url":"https://scholarsarchive.byu.edu/do/oai/"},"display":{"title":"The Relationship Between the Minimal Rank of a Tree and the Rank-Spreads of the Vertices and Edges","abstract":"Let F be a field, G = (V,E) be an undirected graph on n vertices, and let S(F,G) be the set of all symmetric n × n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. Let mr(F,G)be the minimum rank over all matrices in S(F,G). We give a field independent proof of a well-known result that for a tree the sum of its path cover number and minimal rank is equal to the number of vertices in the tree. The rank-spread of a vertex v of G is the difference between the minimal ranks of G and G - v, the graph obtained by deleting v and all its incident edges from G. The rank-spread of an edge is defined similarly. We derive a formula that expresses the minimal rank of a tree as the difference of sums of rank-spreads, the first being the sum of the rank-spreads of all the vertices and the second the sum of the rank-spreads of all the edges. We show that this is a special case of a more general inequality for all graphs. In proving the above results we explore how rank-spreads change as graphs are vertex-summed.","abstract_html":"Let F be a field, G = (V,E) be an undirected graph on n vertices, and let S(F,G) be the set of all symmetric n × n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. Let mr(F,G)be the minimum rank over all matrices in S(F,G). We give a field independent proof of a well-known result that for a tree the sum of its path cover number and minimal rank is equal to the number of vertices in the tree. The rank-spread of a vertex v of G is the difference between the minimal ranks of G and G - v, the graph obtained by deleting v and all its incident edges from G. The rank-spread of an edge is defined similarly. We derive a formula that expresses the minimal rank of a tree as the difference of sums of rank-spreads, the first being the sum of the rank-spreads of all the vertices and the second the sum of the rank-spreads of all the edges. We show that this is a special case of a more general inequality for all graphs. In proving the above results we explore how rank-spreads change as graphs are vertex-summed.","abstract_has_math":false,"creators":["Sinkovic, John Henry"],"institution":"Brigham Young University - Provo","degree_name":"MS","degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-07-24T01:28:46Z","subjects":["minimal rank","rank-spread","tree","Mathematics"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://scholarsarchive.byu.edu/etd/1110","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Sinkovic, John Henry"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2006-12-01T08:00:00Z"]},{"key":"dc:publisher","label":"Institution","values":["Brigham Young University - Provo"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["minimal rank","rank-spread","tree","Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://scholarsarchive.byu.edu/etd/1110","https://scholarsarchive.byu.edu/context/etd/article/2109/viewcontent/ETD_CISOPTR_869.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Physical and Mathematical Sciences; Mathematics"]},{"key":"dc:description.abstract","label":"Abstract","values":["Let F be a field, G = (V,E) be an undirected graph on n vertices, and let S(F,G) be the set of all symmetric n × n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. Let mr(F,G)be the minimum rank over all matrices in S(F,G). We give a field independent proof of a well-known result that for a tree the sum of its path cover number and minimal rank is equal to the number of vertices in the tree. The rank-spread of a vertex v of G is the difference between the minimal ranks of G and G - v, the graph obtained by deleting v and all its incident edges from G. The rank-spread of an edge is defined similarly. We derive a formula that expresses the minimal rank of a tree as the difference of sums of rank-spreads, the first being the sum of the rank-spreads of all the vertices and the second the sum of the rank-spreads of all the edges. We show that this is a special case of a more general inequality for all graphs. In proving the above results we explore how rank-spreads change as graphs are vertex-summed."]},{"key":"dc:format","label":"Dc Format","values":["application:pdf"]},{"key":"dc:source","label":"Dc Source","values":["Brigham Young University - Provo"]},{"key":"dc:title","label":"Title","values":["The Relationship Between the Minimal Rank of a Tree and the Rank-Spreads of the Vertices and Edges"]}]}],"canonical_facts":{"dc:creator":["Sinkovic, John Henry"],"dc:date":["2006-12-01T08:00:00Z"],"dc:description":["Physical and Mathematical Sciences; Mathematics"],"dc:description.abstract":["Let F be a field, G = (V,E) be an undirected graph on n vertices, and let S(F,G) be the set of all symmetric n × n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. Let mr(F,G)be the minimum rank over all matrices in S(F,G). We give a field independent proof of a well-known result that for a tree the sum of its path cover number and minimal rank is equal to the number of vertices in the tree. The rank-spread of a vertex v of G is the difference between the minimal ranks of G and G - v, the graph obtained by deleting v and all its incident edges from G. The rank-spread of an edge is defined similarly. We derive a formula that expresses the minimal rank of a tree as the difference of sums of rank-spreads, the first being the sum of the rank-spreads of all the vertices and the second the sum of the rank-spreads of all the edges. We show that this is a special case of a more general inequality for all graphs. In proving the above results we explore how rank-spreads change as graphs are vertex-summed."],"dc:format":["application:pdf"],"dc:identifier":["https://scholarsarchive.byu.edu/etd/1110","https://scholarsarchive.byu.edu/context/etd/article/2109/viewcontent/ETD_CISOPTR_869.pdf"],"dc:language":["English"],"dc:publisher":["Brigham Young University - Provo"],"dc:source":["Brigham Young University - Provo"],"dc:subject":["minimal rank","rank-spread","tree","Mathematics"],"dc:title":["The Relationship Between the Minimal Rank of a Tree and the Rank-Spreads of the Vertices and Edges"],"dc:type":["Thesis"],"thesis:degree_name":["MS"]},"updated_at":"2026-07-24T01:28:46Z"}