On some conjectures concerning critical independent sets of a graph

MaRDI QIDQ2629485zbMATH OpenFDO

Authors Taylor Short

Publication date 6 July 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.05057, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p43

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

König-Egerváry graphmaximum critical independent setmaximum independent setmaximum 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: Let $G$ be a simple graph with vertex set $V(G)$. A set $SsubseteqV(G)$ is independent if no two vertices from $S$ are adjacent. For $XsubseteqV(G)$, the difference of $X$ is $d(X)=|X|-|N(X)|$ and an independent set $A$ is critical if $d(A)=maxd(X):XsubseteqV(G)extisanindependentset$ (possibly $A=emptyset$). Let $extnucleus(G)$ and $extdiadem(G)$ be the intersection and union, respectively, of all maximum size critical independent sets in $G$. In this paper, we will give two new characterizations of K"{o}nig-Egerv'{a}ry graphs involving $extnucleus(G)$ and $extdiadem(G)$. We also prove a related lower bound for the independence number of a graph. This work answers several conjectures posed by Jarden, Levit, and Mandrescu.

Review text

Summary: Let \(G\) be a simple graph with vertex set \(V(G)\). A set \(S\subseteq V(G)\) is independent if no two vertices from \(S\) are adjacent. For \(X\subseteq V(G)\), the difference of \(X\) is \(d(X) = |X|-|N(X)|\) and an independent set \(A\) is critical if \(d(A) = \max \{d(X): X\subseteq V(G)\text{ is an independent set}\}\) (possibly \(A=\emptyset\)). Let \(\text{nucleus}(G)\) and \(\text{diadem}(G)\) be the intersection and union, respectively, of all maximum size critical independent sets in \(G\). In this paper, we will give two new characterizations of König-Egerváry graphs involving \(\text{nucleus}(G)\) and \(\text{diadem}(G)\). We also prove a related lower bound for the independence number of a graph. This work answers several conjectures posed by \textit{A. Jarden}, \textit{V. E. Levit} and \textit{E. Mandrescu} [``Critical and maximum independent sets of a graph, Preprint, \url{arXiv:1506.00255}].

Recommendations

• Critical and maximum independent sets of a graph
• Problems on matchings and independent sets of a graph
• Critical independent sets of König-Egerváry graphs
• The critical independence number and an independence decomposition
• On König-Egerváry collections of maximum critical independent sets

Cites work

• A characterization of the graphs in which the transversal number equals the matching number
• A note on critical independence reductions
• A set and collection lemma
• An efficiently solvable graph partition problem to which many problems are reducible
• Combinatorial properties of the family of maximum stable sets of a graph
• Critical and maximum independent sets of a graph
• Ear-decompositions of matching-covered graphs
• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
• Graphs with equal independence and annihilation numbers
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• On \(\alpha^{+}\)-stable König-Egerváry graphs
• On maximum matchings in König-Egerváry graphs
• On the number of vertices belonging to all maximum stable sets of a graph
• Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
• Testing for Equality between Maximum Matching and Minimum Node Covering
• The critical independence number and an independence decomposition
• Using critical sets to solve the maximum independent set problem
• Vertices belonging to all critical sets of a graph

Cited in

(19)

• Critical hypergraphs and interesting set-pair systems
• Critical and maximum independent sets of a graph
• Problems on matchings and independent sets of a graph
• Critical independent sets and König-Egerváry graphs
• On the structure of the minimum critical independent set of a graph
• Critical independent sets of König-Egerváry graphs
• Some more updates on an annihilation number conjecture: pros and cons
• Critical and maximum independent sets revisited
• Monotonic properties of collections of maximum independent sets of a graph
• Two more characterizations of König-Egerváry graphs
• A note on graphs contraction-critical with respect to independence number
• On k-independence critical graphs
• scientific article; zbMATH DE number 6806045 (Why is no real title available?)
• Duality and hereditary König-Egerváry set-systems
• On an annihilation number conjecture
• CRITICAL DUAL SET-SYSTEMS
• On König-Egerváry collections of maximum critical independent sets
• On the number of independent sets in damaged Cayley graphs
• On König-Egerváry corona graphs

This page was built for publication: On some conjectures concerning critical independent sets of a graph

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