Skip to main navigation Skip to search Skip to main content

The number of connected components in a graph associated with a rectangular (0, 1)-matrix

  • Sheng Chen*
  • , Li Liang
  • , Yunbo Tian
  • *Corresponding author for this work
  • Harbin Institute of Technology

Research output: Contribution to journalArticlepeer-review

Abstract

With a nonzero rectangular (0,1)-matrix A we associate an undirected graph GA that corresponds to the linear transformation X→AXTA. We use the generalized singular-value decomopsition of incidence matrices to count the number of connected components and the number of bipartite connected components of GA. We show that GA is connected if and only if GA has no bipartite connected component or isolated vertex. We also show that if A has no row or column of 0's, then the number of connected components is 12s(s+1) and the number of bipartite connected components is 12s(s-1), where s is the number of chainable components of A, that is, the number of connected components in the undirected graph with adjacency matrix(OAATO).

Original languageEnglish
Article number13371
Pages (from-to)74-85
Number of pages12
JournalLinear Algebra and Its Applications
Volume487
DOIs
StatePublished - 15 Dec 2015

Keywords

  • Adjacency matrix
  • Chainable matrix
  • Connected component
  • Incidence matrix
  • Tensor product
  • Undirected graph

Fingerprint

Dive into the research topics of 'The number of connected components in a graph associated with a rectangular (0, 1)-matrix'. Together they form a unique fingerprint.

Cite this