TY - JOUR
T1 - Minimum rank and path cover number for generalized and double generalized cycle star graphs
AU - Perdigão, Cecília
AU - Fonseca, Amélia
N1 - info:eu-repo/grantAgreement/FCT/5876/147204/PT#
info:eu-repo/grantAgreement/FCT/5876/147208/PT#
This work was partially supported by the "Fundacao para a Ciencia e Tecnologia" (Portuguese Foundation for Science and Technology) through the project UID/MAT/00297/2013 (Centro de Matematica e Aplicacoes).
This work was partially supported by the "Fundacao para a Ciencia e Tecnologia" (Portuguese Foundation for Science and Technology) through the project UID/MAT/04721/2013 (Centro de Analise Funcional e Estruturas Lineares).
PY - 2018/10/1
Y1 - 2018/10/1
N2 - For a given connected (undirected) graph G=(V,E), with V={1,…,n}, the minimum rank of G is defined to be the smallest possible rank over all symmetric matrices A=[aij] such that for i≠j, aij=0 if, and only if, {i,j}∉E. 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. When G is a tree, the values of the minimum rank and of the path cover number are known as well the relationship between them. We study these values and their relationship for all graphs that have at most two vertices of degree greater than two: generalized cycle stars and double generalized cycle stars.
AB - For a given connected (undirected) graph G=(V,E), with V={1,…,n}, the minimum rank of G is defined to be the smallest possible rank over all symmetric matrices A=[aij] such that for i≠j, aij=0 if, and only if, {i,j}∉E. 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. When G is a tree, the values of the minimum rank and of the path cover number are known as well the relationship between them. We study these values and their relationship for all graphs that have at most two vertices of degree greater than two: generalized cycle stars and double generalized cycle stars.
KW - Cycle
KW - Double generalized cycle star
KW - Generalized cycle star
KW - Generalized star
KW - Graphs
KW - Maximum multiplicity
KW - Minimum rank
KW - Path cover number
KW - Symmetric matrices
UR - http://www.scopus.com/inward/record.url?scp=85047871391&partnerID=8YFLogxK
U2 - 10.1016/j.laa.2018.05.016
DO - 10.1016/j.laa.2018.05.016
M3 - Article
AN - SCOPUS:85047871391
VL - 554
SP - 146
EP - 169
JO - Linear Algebra and its Applications
JF - Linear Algebra and its Applications
SN - 0024-3795
ER -