The extendability of matchings in strongly regular graphs (Q405235): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05E30 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C51 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05B15 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05B05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C70 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6340201 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
strongly regular graphs | |||
Property / zbMATH Keywords: strongly regular graphs / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
matchings | |||
Property / zbMATH Keywords: matchings / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
extendability | |||
Property / zbMATH Keywords: extendability / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
triangular graphs | |||
Property / zbMATH Keywords: triangular graphs / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Latin square graphs | |||
Property / zbMATH Keywords: Latin square graphs / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
block graphs of Steiner systems | |||
Property / zbMATH Keywords: block graphs of Steiner systems / rank | |||
Normal rank |
Revision as of 18:18, 29 June 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The extendability of matchings in strongly regular graphs |
scientific article |
Statements
The extendability of matchings in strongly regular graphs (English)
0 references
4 September 2014
0 references
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.
0 references
strongly regular graphs
0 references
matchings
0 references
extendability
0 references
triangular graphs
0 references
Latin square graphs
0 references
block graphs of Steiner systems
0 references