Relation between the nullity of a graph and its matching number

DOI10.1016/J.DAM.2022.01.020MaRDI QIDQ833002zbMATH OpenOpenAlexFDO

Authors Qi Zhou, Dein Wong, Fenglei Tian

Publication date 28 March 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2022.01.020

zbMATH Keywords

eigenvalue multiplicitymatching numbernullity

Mathematics Subject Classification ID

Connectivity (05C40) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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.

Recommendations

• No graph with nullity \(\eta(G) = | V(G) | - 2 m(G) + 2 c(G) - 1\)
• Characterization of graphs with given order, given size and given matching number that minimize nullity
• An improved lower bound for the nullity of a graph in terms of matching number
• Bounds for the nullity of a graph in terms of the matching number and the independence number
• The nullity of bicyclic graphs in terms of their matching number

Cites work

• A characterization of graphs \(G\) with nullity \(|V(G)|-2m(G)+2c(G)\)
• An improved lower bound for the nullity of a graph in terms of matching number
• Bounds for the matching number, the edge chromatic number and the independence number of a graph in terms of rank
• Characterization of graphs with given order, given size and given matching number that minimize nullity
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 3414355 (Why is no real title available?)
• On the nullity of line graphs of trees
• Spectra of graphs
• Spektren endlicher Grafen
• The multiplicity of an arbitrary eigenvalue of a graph in terms of cyclomatic number and number of pendant vertices

Cited in

(12)

• The nullity of a graph with fractional matching number
• The rank of a signed graph
• No graph with nullity \(\eta(G) = | V(G) | - 2 m(G) + 2 c(G) - 1\)
• Characterization of graphs with given order, given size and given matching number that minimize nullity
• Bounds for the nullity of a graph in terms of the matching number and the independence number
• On the nullity number of graphs
• An improved lower bound for the nullity of a graph in terms of matching number
• A survey of the maximal and the minimal nullity in terms of omega invariant on graphs
• Characterization of graphs with rank 2v(G) - 2(G) - 2c(G) + 1
• The multiplicity of nonzero eigenvalues and the induced matching number of a graph
• Improved bounds on the H-rank of a mixed graph in terms of the matching number and fractional matching number
• Relation between the rank of a signed graph and the fractional matching number of its underlying graph

This page was built for publication: Relation between the nullity of a graph and its matching number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q833002)