On some conjectures concerning critical independent sets of a graph. (English) Zbl 1339.05296
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 A. Jarden, V. E. Levit and E. Mandrescu [“Critical and maximum independent sets of a graph”, Preprint, arXiv:1506.00255].
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C35 | Extremal problems in graph theory |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
Keywords:
maximum independent set; maximum critical independent set; König-Egerváry graph; maximum matchingReferences:
| [1] | E. Boros, M. C. Golumbic, and V. E. Levit, On the number of vertices belonging to all maximum stable sets of a graph, Discrete Applied Mathematics 124 (2002), 17-25. · Zbl 1010.05058 |
| [2] | S. Butenko and S. Trukhanov, Using critical sets to solve the maximum independent set problem, Operations Research Letters 35 (2007), 519-524. · Zbl 1149.90375 |
| [3] | R. W. Deming, Independence Number of Graphs - an Extension of the K¨onig-Egerv´ary Theorem, Discrete Mathematics 27 (1979), 23-33. · Zbl 0404.05034 |
| [4] | E. Egerv´ary, On combinatorial properties of matrices, Matematikai Lapok 38 (1931), 16-28. · JFM 57.1340.03 |
| [5] | M. Garey and D. Johnson, Computers and Intractability, W. H. Freeman and Company, New York, 1979. · Zbl 0411.68039 |
| [6] | F. Gavril, Testing for equality between maximum matching and minimum node covering, Inf. Process. Lett. 6 (1977), no. 6, 199-202. · Zbl 0367.05056 |
| [7] | F. Gavril, An efficient solvable graph partition problem to which many problems are reducible, Information Processing Letters 45 (1993), no. 285-290. · Zbl 0768.68140 |
| [8] | A. Jarden, V. E. Levit, and E. Mandrescu, Critical and Maximum Independent Sets of a Graph,arXiv:1506.00255(2015), 12 pp. · Zbl 1394.05089 |
| [9] | A. Jarden, V. E. Levit, and E. Mandrescu, Monotonic Properties of Collections of Maximum Independent Sets of a Graph,arXiv:1506.00249(2015), 15 pp. · Zbl 1394.05089 |
| [10] | D. K¨onig, Graphen und Matrizen, Matematikai Lapok 38 (1931), 116-119. · JFM 57.1340.04 |
| [11] | E. Korach, T. Nguyen, and B. Peis, Subgraph characterization of red/blue-split graphs and K¨onig-Egerv´ary graphs, Proceedings of the seventeenth annual acm-siam symposium on discrete algorithms, 2006, pp. 842-850. · Zbl 1192.05116 |
| [12] | C. E. Larson, A Note on Critical Independence Reductions, Bulletin of the Institute of Combinatorics and its Applications 51 (2007), 34-46. · Zbl 1135.05051 |
| [13] | C. E. Larson, The critical independence number and an independence decomposition, European Journal of Combinatorics 32 (2011), 294-300. · Zbl 1230.05226 |
| [14] | C. E. Larson and R. Pepper, Graphs with equal independence and annihilation numbers, The Electronic Journal of Combinatorics 18 (2011), no. 1, #P180. · Zbl 1238.05198 |
| [15] | V. E. Levit and E. Mandrescu, Combinatorial properties of the family of maximum stable sets of a graph, Discrete Applied Mathematics 117 (2002), 149-161. the electronic journal of combinatorics 23(2) (2016), #P2.439 · Zbl 0992.05062 |
| [16] | V. E. Levit and E. Mandrescu, On α+-stable K¨onig-Egerv´ary graphs, Discrete Mathematics 263 (2003), 179-190. · Zbl 1017.05086 |
| [17] | V. E. Levit and E. Mandrescu, Vertices belonging to all critical independent sets of a graph, SIAM Journal on Discrete Mathematics 26 (2012), 399-403. · Zbl 1246.05122 |
| [18] | V. E. Levit and E. Mandrescu, On maximum matchings in K¨onig-Egerv´ary graphs, Discrete Applied Mathematics 161 (2013), 1635-1638. · Zbl 1287.05119 |
| [19] | V. E. Levit and E. Mandrescu, A set and collection lemma, The Electronic Journal of Combinatorics 21 (2014), no. P1.40. · Zbl 1300.05230 |
| [20] | L. Lov´asz, Ear-decompositions of matching-covered graphs, Combinatorica 3 (1983), 105-118. · Zbl 0516.05047 |
| [21] | T. Short, KE theory & the number of vertices belonging to all maximum independent sets in a graph, Master’s Thesis,http://scholarscompass.vcu.edu/etd/2353/, 2011. |
| [22] | F. Sterboul, A characterization of the graphs in which transversal number equals the matching number, Journal of Combinatorial Theory Series B 27 (1979), no. 228-229. · Zbl 0415.05032 |
| [23] | D. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, Inc., Upper Saddle River, NJ, 2001. |
| [24] | C. Q. Zhang, Finding critical independent sets and crtitical vertex subsets are polynomial problems, SIAM Journal on Discrete Mathematics 3 (1990), 431-438. · Zbl 0756.05095 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
