The hardness of the independence and matching clutter of a graph

DOI10.7494/OPMATH.2016.36.3.375zbMATH1335.05131MaRDI QIDQ2805262FDOQ2805262

Authors Sasun Hambardzumyan, Vahan V. Mkrtchyan, Vahe L. Musoyan, Hovhannes Sargsyan

Publication date 10 May 2016

Published in Opuscula Mathematica (Search for Journal in Brave)

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

zbMATH Keywords

matchinghardnessindependent setmaximal independent setcluttermaximal matching

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A {it clutter} (or {it antichain} or {it Sperner family}) $L$ is a pair $(V,E)$, where $V$ is a finite set and $E$ is a family of subsets of $V$ none of which is a subset of another. Usually, the elements of $V$ are called {it vertices} of $L$, and the elements of $E$ are called {it edges} of $L$. A subset $s_e$ of an edge $e$ of a clutter is called {it recognizing} for $e$, if $s_e$ is not a subset of another edge. The {it hardness} of an edge $e$ of a clutter is the ratio of the size of $eextrm\text{'}s$ smallest recognizing subset to the size of $e$. The hardness of a clutter is the maximum hardness of its edges. We study the hardness of clutters arising from independent sets and matchings of graphs.

Recommendations

• A tight lower bound for the hardness of clutters
• Blocker size via matching minors
• Ideal clutters
• Uniform clutters and dominating sets of graphs
• Publication:3211359

Cites work

• Randomly matchable graphs

Cited in

(2)

• A tight lower bound for the hardness of clutters
• Uniform clutters and dominating sets of graphs

This page was built for publication: The hardness of the independence and matching clutter of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2805262)