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

DOI10.1016/J.DAM.2024.01.001MaRDI QIDQ6202947zbMATH OpenOpenAlexWikidataFDO

Authors Shujing Miao, Shuchao Li, Wei Wei

Publication date 27 February 2024

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

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)

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.

Recommendations

• Matching extension and distance spectral radius
• Matching extension and minimum degree
• Forbidden pairs for the matching extendability of graphs with connectivity at least 2 or 3
• Matchings and matching extensions in graphs
• Binding number conditions for matching extension

Cites work

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

Cited in

(1)

• Matching extension and distance spectral radius

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)