On the extendability of quasi-strongly regular graphs with diameter 2
A graph \(G\) with an even number of vertices at least \(2l+2\) vertices is \(l\)-extendable if each matching of size \(l\) is contained in a perfect matching of \(G\). A graph \(G\) is quasi-strongly regular with parameters \((n,k,\lambda;\mu_1,\dots,\mu_s)\) if \(G\) is \(k\)-regular on \(n\) vertices, any two adjacent vertices of \(G\) have exactly \(\lambda\) common neighbors, while any two nonadjacent vertices of \(G\) have either \(\mu_1\) or \dots\ or \(\mu_s\) common neighbors. The authors show that a quasi-strongly regular graph with parameters \((n,k,\lambda;\mu_1,\mu_2)\), \(n\geq 6\), \(\mu_1>\mu_2\geq 1\), is not 2-extendable if and only if it is either the complete multipartite graph \(K_{2,2,2}\), or the Möbius ladder on eight vertices, or the Petersen graph, or the lexicographic product \(C_5[2K_1]\).
- Extending matchings in graphs: A survey
- Graph theory
- Hamiltonian cycles in n‐extendable graphs
- scientific article; zbMATH DE number 4066957 (Why is no real title available?)
- scientific article; zbMATH DE number 166088 (Why is no real title available?)
- scientific article; zbMATH DE number 166089 (Why is no real title available?)
- scientific article; zbMATH DE number 238423 (Why is no real title available?)
- Max-cut and extendability of matchings in distance-regular graphs
- Maximum degree in graphs of diameter 2
- Notes on factor-criticality, extendibility and independence number
- On 2-extendable abelian Cayley graphs
- On extendability of Cayley graphs
- On extendability of Deza graphs with diameter 2
- On n-extendable graphs
- On quasi-strongly regular graphs
- On regular \((2,q)\)-extendable graphs.
- On regular factors in regular graphs with small radius
- The 2-extendability of strongly regular graphs
- The extendability of matchings in strongly regular graphs
- The 2-extendability of strongly regular graphs
- On extendability of co-edge-regular graphs
- Some constructions of quasi-strongly regular digraphs
- On the second neighbourhoods of quasi-strongly regular graphs
- On extendability of Deza graphs with diameter 2
- On quasi-strongly regular graphs
- scientific article; zbMATH DE number 166088 (Why is no real title available?)
- On quasi-strongly regular graphs with parameters \((n, k, a; k - 2, c_2)\) for \(a < k - 5\)
- Maximizing the minimum and maximum forcing numbers of perfect matchings of graphs
- The classification of \(2\)-extendable edge-regular graphs with diameter \(2\)
- On the fractional matching extendability of Cayley graphs of abelian groups
This page was built for publication: On the extendability of quasi-strongly regular graphs with diameter 2
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2413638)
