Minimum rank and path cover number for generalized and double generalized cycle star graphs

Cecília Perdigão, Amélia Fonseca

Research output: Contribution to journalArticle

5 Downloads (Pure)

Abstract

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.

Original languageEnglish
Pages (from-to)146-169
Number of pages24
JournalLinear Algebra and Its Applications
Volume554
DOIs
Publication statusPublished - 1 Oct 2018

Keywords

  • Cycle
  • Double generalized cycle star
  • Generalized cycle star
  • Generalized star
  • Graphs
  • Maximum multiplicity
  • Minimum rank
  • Path cover number
  • Symmetric matrices

Fingerprint Dive into the research topics of 'Minimum rank and path cover number for generalized and double generalized cycle star graphs'. Together they form a unique fingerprint.

  • Cite this