Positive semidefinite zero forcing numbers of two classes of graphs

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

3 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)44-54
Journal / PublicationTheoretical Computer Science
Volume786
Online published7 May 2018
Publication statusPublished - 27 Sep 2019

Abstract

The positive semidefinite zero forcing number is a variant of the zero forcing number, which is an important parameter in the study of minimum rank/maximum nullity problems. In this paper, we consider two classes of graphs: matching-chain graphs and claw-free graphs. We first introduce the propagation decomposition of graphs; then we use this decomposition to prove a lower bound for the positive semidefinite zero forcing number of a graph. We apply this lower bound to find the positive semidefinite zero forcing number of matching-chain graphs. We show that the positive semidefinite zero forcing number and the zero forcing number agree for matching-chain graphs. As a consequence, we prove the conjecture about the positive semidefinite zero forcing number of the Cartesian product of two paths, and partially prove the conjecture about the positive semidefinite zero forcing number of the Cartesian product of a cycle and a path. For claw-free graphs, we establish a relationship between the positive semidefinite zero forcing number and the zero forcing number. We also prove that it is NP-complete to find the positive semidefinite zero forcing number of line graphs.

Research Area(s)

  • Maximum positive semidefinite nullity, Minimum rank, Positive semidefinite zero forcing number, Zero forcing number

Citation Format(s)