Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids (Q2462380): Difference between revisions

A matching \(M\) is uniquely restricted in a graph \(G\) if its saturated vertices induce a subgraph which has a unique perfect matching. \(G\) is a König-Egerváry graph provided \(\alpha(G) + \mu(G) = | V(G)| \), where is \(\mu(G)\) the size of a maximum matching and \(\alpha(G)\) the cardinality of a maximum stable set. \(S\) is a local maximum stable set of \(G\), writen \(S\in \Psi(G)\), if \(S\) is a maximum stable set of the subgraph spanned by \(S\cup N(S)\), where \(N(S)\) is the neighborhood of \(S\). We say that \(\Psi(G)\) is a greedoid on its vertex set if and only if all its maximum matchings are uniquely restricted. The authors demonstrate that if \(G\) is a triangle-free graph, then \(\Psi(G)\) is a greedoid if and only if all its maximum matchings are uniquely restricted and, for any \(S\in \Psi(G)\), the subgraph spanned by \(S\cup N(S)\) is a König-Egerváry graph.