Spectral characterization of matchings in graphs

DOI10.1016/J.LAA.2016.02.004MaRDI QIDQ5965406zbMATH OpenOpenAlexFDO

Authors Keivan Hassani Monfared, Sudipta Mallik

Publication date 3 March 2016

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.03590

zbMATH Keywords

Jacobian methodmatchingskew-symmetric matrixspectrumstructured inverse eigenvalue problem

Mathematics Subject Classification ID

Trees (05C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Numerical solutions to inverse eigenvalue problems (65F18)

Abstract: A spectral characterization of the matching number (the size of a maximum matching) of a graph is given. More precisely, it is shown that the graphs G of order n whose matching number is k are precisely those graphs with the maximum skew rank 2k such that for any given set of k distinct nonzero purely imaginary numbers there is a real skew-symmetric matrix A with graph G whose spectrum consists of the given k numbers, their conjugate pairs, and n-2k zeros.

Recommendations

• Matchings in graphs from the spectral radius
• Spectral radius of graphs with given matching number
• The maximal A_α-spectral radius of graphs with given matching number
• The maximum spectral radius of \(t\)-connected graphs with bounded matching number
• On the maximal α-spectral radius of graphs with given matching number

Cites work

• Construction of matrices with a given graph and prescribed interlaced spectral data
• Construction of real skew-symmetric matrices from interlaced spectral data, and graph
• scientific article; zbMATH DE number 1765103 (Why is no real title available?)
• Matching theory
• Matrix Analysis
• Minimum rank of skew-symmetric matrices described by a graph
• On eigenvalues of matrices dependent on a parameter
• The Factorization of Linear Graphs

Cited in

(7)

• Matchings in regular graphs from eigenvalues
• A zero forcing technique for bounding sums of eigenvalue multiplicities
• On the spectrum of the perfect matching derangement graph
• A note on skew spectrum of graphs.
• Anti-forcing spectra of perfect matchings of graphs
• An extremal problem on Q-spectral radii of graphs with given size and matching number
• Towards a structural characterization of unimodular graphs with a unique perfect matching

This page was built for publication: Spectral characterization of matchings in graphs

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