Max-cut and extendability of matchings in distance-regular graphs

DOI10.1016/j.ejc.2017.01.001zbMath1358.05083arXiv1507.06254OpenAlexW1432662476MaRDI QIDQ518196

Jack H. Koolen, Weiqiang Li, Sebastian M. Cioabă

Publication date: 28 March 2017

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

\(t\)-extendable connected graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Connectivity (05C40)

Related Items (8)

On the extendability of quasi-strongly regular graphs with diameter 2 ⋮ On the connectivity of graphs in association schemes ⋮ The extendability of Cayley graphs generated by transpositions ⋮ The classification of \(2\)-extendable edge-regular graphs with diameter \(2\) ⋮ Connectivity concerning the last two subconstituents of a \(Q\)-polynomial distance-regular graph ⋮ Unnamed Item ⋮ On extendability of co-edge-regular graphs ⋮ Matching extendability and connectivity of regular graphs from eigenvalues

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distance-regular graphs
• On the connectedness of the complement of a ball in distance-regular graphs
• The extendability of matchings in strongly regular graphs
• Spectra of graphs
• Distance-regular graphs with or at least half the valency
• Combinatorial properties and the complexity of a max-cut approximation
• The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
• On a conjecture of Brouwer involving the connectivity of strongly regular graphs
• New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph
• The vertex-connectivity of a distance-regular graph
• On \(k\)-walk-regular graphs
• On n-extendable graphs
• Equiarboreal graphs
• The distance-regular graphs of valency four
• Laplacian eigenvalues and the maximum cut problem
• Extending matchings in graphs: A survey
• There exists no distance-regular graph with intersection array \((5,4,3;1,1,2)\)
• Matchings and matching extensions in graphs
• Eigenvalues and perfect matchings
• The 2-extendability of strongly regular graphs
• Large incidence-free sets in geometries
• Semidefinite programs and association schemes
• Construction for bicritical graphs and \(k\)-extendable bipartite graphs
• Disconnecting strongly regular graphs
• Spectral and Geometric Properties of k-Walk-Regular Graphs
• Recent Progress in Matching Extension
• Graph Factors and Matching Extensions
• Cubic Distance-Regular Graphs
• Extremal graphs without three‐cycles or four‐cycles
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Max Cut and the Smallest Eigenvalue
• Bipartite Subgraphs and the Smallest Eigenvalue
• Reducibility among Combinatorial Problems
• Three Remarkable Graphs
• On the structure of factorizable graphs. II
• The Factorization of Linear Graphs

This page was built for publication: Max-cut and extendability of matchings in distance-regular graphs