Combinatorial and spectral properties of König-Egerváry graphs

DOI10.1016/j.dam.2016.09.042zbMath1358.05171OpenAlexW2535524988MaRDI QIDQ516875

María Robbiano, Oscar Rojo, Domingos Moreira Cardoso

Publication date: 15 March 2017

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

Full work available at URL: https://doi.org/10.1016/j.dam.2016.09.042

zbMATH Keywords

Laplacian eigenvaluesadjacency eigenvaluesKönig-Egerváry graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (4)

Critical and maximum independent sets of a graph ⋮ The maximum number of maximum dissociation sets in trees ⋮ Some variants of perfect graphs related to the matching number, the vertex cover and the weakly connected domination number ⋮ New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs
• On the Laplacian and signless Laplacian spectrum of a graph with \(k\) pairwise co-neighbor vertices
• Dominating induced matchings for \(P_7\)-free graphs in linear time
• A characterization of the graphs in which the transversal number equals the matching number
• Spectra of graphs
• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• Efficient edge domination in regular graphs
• Ear-decompositions of matching-covered graphs
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• Laplacian matrices of graphs: A survey
• Proof of conjectures on adjacency eigenvalues of graphs
• On the number of vertices belonging to all maximum stable sets of a graph
• Interlacing eigenvalues and graphs
• Two more characterizations of König-Egerváry graphs
• On maximum matchings in König-Egerváry graphs
• A Polynomial-time Algorithm for the Dominating Induced Matching Problem in the Class of Convex Graphs
• A characterization of Konig-Egervary graphs using a common property of all maximum matchings
• Efficient Edge Domination on Hole-Free Graphs in Polynomial Time
• Dominating Induced Matchings
• Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs

This page was built for publication: Combinatorial and spectral properties of König-Egerváry graphs