Anzeige
Erschienen in:
07.11.2019
On the zero forcing number of a graph involving some classical parameters
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2020
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Given a simple graph G, let \(Z(G),\, p(G),\, \Phi (G), ex(G)\) and M(G), respectively, be the zero forcing number, the number of pendant vertices, the cyclomatic number, the number of exterior major vertices and the maximum nullity of G. Wang et al. (Linear Multilinear Algebra, 2018. https://doi.org/10.1080/03081087.2018.1545829) established upper and lower bounds on Z(G) with respect to \(p(G),\, ex(G)\) and \(\Phi (G)\): \(p(G)-ex(G)-1\leqslant Z(G)\leqslant p(G)+2\Phi (G)+1\). Hence, it is interesting to study the distribution of the zero forcing number Z(G) in the interval \([p(G)-ex(G)-1,\, p(G)+2\Phi (G)+1]\). Wang et al. (2018) determined all the connected graphs G with \(Z(G)=p(G)-ex(G)\) and \(Z(G)=p(G)+2\Phi (G)-1.\) In this paper we identify all the connected graphs G with \(Z(G)=p(G)-ex(G)+1\) and \(Z(G)=p(G)+2\Phi (G)-2.\) On the other hand, ‘AIM Minimum Rank-Special Graphs Work Group’ (Linear Algebra Appl 428(7):1628–1648, 2008) established the inequality \(Z(G)\geqslant M(G)\). The authors posted an attractive question: What is the class of graphs G for which \(Z(G)=M(G)\)? In this paper, we show that the equality holds for threshold graphs.