The extendability of matchings in strongly regular graphs
block graphs of Steiner systemsextendabilityLatin square graphsmatchingsstrongly regular graphstriangular graphs
Combinatorial aspects of block designs (05B05) Orthogonal arrays, Latin squares, Room squares (05B15) Graph designs and isomorphic decomposition (05C51) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Association schemes, strongly regular graphs (05E30)
Summary: A graph \(G\) of even order \(v\) is called \(t\)-extendable if it contains a perfect matching, \(t<v/2\) and any matching of \(t\) edges is contained in some perfect matching. The extendability of \(G\) is the maximum \(t\) such that \(G\) is \(t\)-extendable. In this paper, we study the extendability properties of strongly regular graphs. We improve previous results and classify all strongly regular graphs that are not \(3\)-extendable. We also show that strongly regular graphs of valency \(k\geq 3\) with \(\lambda \geq 1\) are \(\lfloor k/3\rfloor\)-extendable (when \(\mu \leq k/2\)) and \(\lceil \frac{k+1}{4}\rceil\)-extendable (when \(\mu>k/2\)), where \(\lambda\) is the number of common neighbors of any two adjacent vertices and \(\mu\) is the number of common neighbors of any two non-adjacent vertices. Our results are close to being best possible as there are strongly regular graphs of valency \(k\) that are not \(\lceil k/2\rceil \)-extendable. We show that the extendability of many strongly regular graphs of valency \(k\) is at least \(\lceil k/2 \rceil -1\) and we conjecture that this is true for all primitive strongly regular graphs. We obtain similar results for strongly regular graphs of odd order.
- 5-chromatic strongly regular graphs
- A course in combinatorics.
- Construction for bicritical graphs and \(k\)-extendable bipartite graphs
- Disconnecting strongly regular graphs
- Distance regular graphs of diameter 3 and strongly regular graphs
- Eigenvalues and perfect matchings
- Exponentially many perfect matchings in cubic graphs
- Extending matchings in graphs: A survey
- Graph Factors and Matching Extensions
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- scientific article; zbMATH DE number 3884175 (Why is no real title available?)
- scientific article; zbMATH DE number 43547 (Why is no real title available?)
- scientific article; zbMATH DE number 50655 (Why is no real title available?)
- scientific article; zbMATH DE number 166088 (Why is no real title available?)
- scientific article; zbMATH DE number 1256777 (Why is no real title available?)
- scientific article; zbMATH DE number 487720 (Why is no real title available?)
- scientific article; zbMATH DE number 1054729 (Why is no real title available?)
- scientific article; zbMATH DE number 2149410 (Why is no real title available?)
- scientific article; zbMATH DE number 238423 (Why is no real title available?)
- scientific article; zbMATH DE number 3211575 (Why is no real title available?)
- scientific article; zbMATH DE number 3390835 (Why is no real title available?)
- Matching theory
- Matchings and matching extensions in graphs
- Matchings in regular graphs from eigenvalues
- N‐extendability of symmetric graphs
- On a conjecture of Brouwer involving the connectivity of strongly regular graphs
- On matching extensions with prescribed and proscribed edge sets. II
- On n-extendable graphs
- On the connectedness of the complement of a ball in distance-regular graphs
- On the structure of factorizable graphs. II
- Random strongly regular graphs?
- Recent Progress in Matching Extension
- Results and open problems in matchings in regular graphs
- Spectra of graphs
- Spherical codes and designs
- Strongly regular graphs with (-1, 1, 0) adjacency matrix having eigenvalue 3
- The 2-extendability of strongly regular graphs
- The connectivity of strongly regular graphs
- The Factorization of Linear Graphs
- The uniqueness of the strongly regular graph on 77 points
- The vertex-connectivity of a distance-regular graph
- Minimal graphs for matching extensions
- The 2-extendability of strongly regular graphs
- The cyclic edge-connectivity of strongly regular graphs
- On extendability of co-edge-regular graphs
- Extendability and criticality in matching theory
- Matching extendability and connectivity of regular graphs from eigenvalues
- On the extendability of quasi-strongly regular graphs with diameter 2
- scientific article; zbMATH DE number 6007655 (Why is no real title available?)
- scientific article; zbMATH DE number 6828923 (Why is no real title available?)
- The chromatic index of strongly regular graphs
- scientific article; zbMATH DE number 166088 (Why is no real title available?)
- scientific article; zbMATH DE number 205826 (Why is no real title available?)
- Max-cut and extendability of matchings in distance-regular graphs
- The extendability of Cayley graphs generated by transpositions
- The classification of \(2\)-extendable edge-regular graphs with diameter \(2\)
- Extending matchings in planar graphs. IV
- On the fractional matching extendability of Cayley graphs of abelian groups
- Eigenvalues and factors: a survey
This page was built for publication: The extendability of matchings in strongly regular graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405235)
