Relation between the nullity of a graph and its matching number
type: Item
instance of: scholarly article
title: Relation between the nullity of a graph and its matching number
zbMATH Open document ID: 1491.05129
author: Qi Zhou
author: Dein Wong
author: Fenglei Tian
published in: Discrete Applied Mathematics
publication date: 2022-03-28T00:00:00Z
review text: Let \(G\) be a connected graph of order \(n(G)\) and size \(e(G)\). The nullity of \(G\), denoted by \(\eta(G)\), is the multiplicity of eigenvalue zero of the adjacency matrix of \(G\). \textit{L. Wang} and \textit{D. Wong} [ibid. 166, 276--281 (2014; Zbl 1283.05226)] bounded \(\eta(G)\) as \[ n(G)-2m(G)-c(G) \le\eta(G) \le n(G)-2m(G) + 2c(G), \] where \(m(G)\) is the matching number of \(G\) and \(c(G)\), defined by \(c(G) = e(G)-n(G) + 1\), is the dimension of cycle space of \(G\). The authors found that the upper and the lower bounds for \(\eta(G)\) both fail to accurate if the edges in \(G\) are dense, namely if \(c(G)\) is large enough. In this paper, the authors improved the above bounds. They proved that \[ n(G)-2m(G)-\sigma(G) \le \eta(G)\le n(G)-2m(G) + 2\omega(G), \] where \(\sigma(G)\) is the largest number of disjoint odd cycles in \(G\) and \(\omega(G)\) is the number of even cycles in \(G\). The cycle-disjoint connected graphs with nullity \(n(G)-2m(G)-\sigma(G)\) were also characterized.
reviewed by: Xiaogang Liu
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 7499199
zbMATH Keywords: eigenvalue multiplicity
zbMATH Keywords: nullity
zbMATH Keywords: matching number
MaRDI profile type: Publication
full work available at URL: j.dam.2022.01.020
OpenAlex ID: W4221030474
cites work: Spectra of graphs
cites work: Spektren endlicher Grafen
cites work: Q3907599
cites work: Q5678898
cites work: On the nullity of line graphs of trees
cites work: An improved lower bound for the nullity of a graph in terms of matching number
cites work: A characterization of graphs \(G\) with nullity \(|V(G)|-2m(G)+2c(G)\)
cites work: Characterization of graphs with given order, given size and given matching number that minimize nullity
cites work: The multiplicity of an arbitrary eigenvalue of a graph in terms of cyclomatic number and number of pendant vertices
cites work: Bounds for the matching number, the edge chromatic number and the independence number of a graph in terms of rank
DOI: 10.1016/J.DAM.2022.01.020
description: scientific article; zbMATH DE number 7499199