Matching extension and matching exclusion via the size or the spectral radius of graphs

DOI10.1016/J.DAM.2024.01.001arXiv2304.12565OpenAlexW4391046883WikidataQ129666141 ScholiaQ129666141MaRDI QIDQ6202947FDOQ6202947

Shujing Miao, Wei Wei, Shuchao Li

Publication date: 27 February 2024

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

Abstract: A graph $G$ is said to be $k$-extendable if every matching of size $k$ in $G$ can be extended to a perfect matching of $G$, where $k$ is a positive integer. We say $G$ is $1$-excludable if for every edge $e$ of $G$, there exists a perfect matching excluding $e$. In this paper, we first establish a lower bound on the size (resp. the spectral radius) of $G$ to guarantee that $G$ is $k$-extendable. Then we determine a lower bound on the size (resp. the spectral radius) of $G$ to guarantee that $G$ is $1$-excludable. All the corresponding extremal graphs are characterized.

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

zbMATH Keywords

sizespectral radiusmatching extensionmatching exclusion

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Matrix Analysis
• Title not available (Why is that?)
• Factors and factorizations of graphs. Proof techniques in factor theory
• Graphs and matrices
• On n-extendable graphs
• Extending matchings in graphs: A survey
• Graph Factors and Matching Extensions
• On defect-d matchings in graphs
• Eigenvalues and perfect matchings
• Tight lower bounds on the size of a maximum matching in a regular graph
• Recent Progress in Matching Extension
• On the spectral radius of graphs with cut edges
• Binding number and toughness for matching extension
• Merging the A-and Q-spectral theories
• Remarks on regular factors of regular graphs
• Regular factors in regular graphs
• Title not available (Why is that?)
• On the spectrum of an equitable quotient matrix and its application
• Title not available (Why is that?)
• Pan-factorial property in regular graphs
• Characterizations for \({\mathcal{P}}_{\geq 2}\)-factor and \({\mathcal{P}}_{\geq 3}\)-factor covered graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Distance matching extension and local structure of graphs
• Spectral radius and matchings in graphs
• Characterizing \(\mathcal{P}_{\geqslant 2} \)-factor and \(\mathcal{P}_{\geqslant 2} \)-factor covered graphs with respect to the size or the spectral radius
• Distance matching extension in cubic bipartite graphs
• Edge proximity and matching extension in projective planar graphs
• On the \(A_\alpha\)-spectral radius of graphs without large matchings
• Title not available (Why is that?)
• Distance restricted matching extension missing vertices and edges in 5‐connected triangulations of the plane

This page was built for publication: Matching extension and matching exclusion via the size or the spectral radius of graphs

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