Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Critical and Maximum Independent Sets Revisited

  • Conference paper
  • First Online:
Mathematical Optimization Theory and Operations Research (MOTOR 2019)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 11548))

  • 978 Accesses

Abstract

Let G be a simple graph with vertex set \(V\left( G\right) \).

A set \(S\subseteq V\left( G\right) \) is independent if no two vertices from S are adjacent, and by \(\mathrm {Ind}(G)\) we mean the family of all independent sets of G.

The number \(d\left( X\right) =\) \(\left| X\right| -\left| N(X)\right| \) is the difference of \(X\subseteq V\left( G\right) \), and a set \(A\in \mathrm {Ind}(G)\) is critical if \(d(A)=\max \{d\left( I\right) :I\in \mathrm {Ind}(G)\}\) [34].

Let us recall the following definitions:

  • \(\mathrm {core}\left( G\right) = {\displaystyle \bigcap } \left\{ S:S\textit{ is a maximum independent set}\right\} \) [16],

  • \(\mathrm {corona}\left( G\right) = {\displaystyle \bigcup } \left\{ S:S\textit{ is a maximum independent set}\right\} \) [5],

  • \(\mathrm {\ker }(G)= {\displaystyle \bigcap } \left\{ S:S\textit{ is a critical independent set}\right\} \) [18],

  • \(\mathrm {nucleus}(G)= {\displaystyle \bigcap } \left\{ S:S\textit{ is a maximum critical independent set}\right\} \) [12]

  • \(\mathrm {diadem}(G)= {\displaystyle \bigcup } \left\{ S:S\textit{ is a (maximum) critical independent set}\right\} \) [24].

In this paper we focus on interconnections between \(\ker \), core, corona, \(\mathrm {nucleus}\), and diadem.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 79.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 99.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Ageev, A.A.: On finding critical independent and vertex sets. SIAM J. Discret. Math. 7, 293–295 (1994)

    Article  MathSciNet  Google Scholar 

  2. Beckenbach, I., Borndörfer, R.: Hall’s and König’s theorem in graphs and hypergraphs. Discret. Math. 341, 2753–2761 (2018)

    Article  Google Scholar 

  3. Bhattacharya, A., Mondal, A., Murthy, T.S.: Problems on matchings and independent sets of a graph. Discret. Math. 341, 1561–1572 (2018)

    Article  MathSciNet  Google Scholar 

  4. Bonomo, F., Dourado, M.C., Durán, G., Faria, L., Grippo, L.N., Safe, M.D.: Forbidden subgraphs and the König-Egerváry property. Discret. Appl. Math. 161, 2380–2388 (2013)

    Article  Google Scholar 

  5. Boros, E., Golumbic, M.C., Levit, V.E.: On the number of vertices belonging to all maximum stable sets of a graph. Discret. Appl. Math. 124, 17–25 (2002)

    Article  MathSciNet  Google Scholar 

  6. Butenko, S., Trukhanov, S.: Using critical sets to solve the maximum independent set problem. Oper. Res. Lett. 35, 519–524 (2007)

    Article  MathSciNet  Google Scholar 

  7. DeLaVina, E.: Written on the Wall II, Conjectures of Graffiti.pc. http://cms.dt.uh.edu/faculty/delavinae/research/wowII/

  8. DeLaVina, E., Larson, C.E.: A parallel algorithm for computing the critical independence number and related sets. Ars Math. Contemp. 6, 237–245 (2013)

    Article  MathSciNet  Google Scholar 

  9. Deming, R.W.: Independence numbers of graphs - an extension of the König-Egerváry theorem. Discret. Math. 27, 23–33 (1979)

    Article  MathSciNet  Google Scholar 

  10. Garey, M., Johnson, D.: Computers and Intractability, 1st edn. W. H. Freeman and Company, New York (1979)

    MATH  Google Scholar 

  11. Jarden, A., Levit, V.E., Mandrescu, E.: Critical and maximum independent sets of a graph. Discret. Appl. Math. 247, 127–134 (2018)

    Article  MathSciNet  Google Scholar 

  12. Jarden, A., Levit, V.E., Mandrescu, E.: Monotonic properties of collections of maximum independent sets of a graph, Order (2018). https://link.springer.com/article/10.1007/s11083-018-9461-8

  13. Korach, E., Nguyen, T., Peis B.: Subgraph characterization of red/blue-split graphs and König-Egerváry graphs. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 842–850. ACM Press (2006)

    Google Scholar 

  14. Larson, C.E.: A note on critical independence reductions. Bull. Inst. Comb. Appl. 5, 34–46 (2007)

    MathSciNet  MATH  Google Scholar 

  15. Larson, C.E.: The critical independence number and an independence decomposition. Eur. J. Comb. 32, 294–300 (2011)

    Article  MathSciNet  Google Scholar 

  16. Levit, V.E., Mandrescu, E.: Combinatorial properties of the family of maximum stable sets of a graph. Discret. Appl. Math. 117, 149–161 (2002)

    Article  MathSciNet  Google Scholar 

  17. Levit, V.E., Mandrescu, E.: On \(\alpha ^{+}\)-stable König-Egerváry graphs. Discret. Math. 263, 179–190 (2003)

    Article  Google Scholar 

  18. Levit, V.E., Mandrescu, E.: Vertices belonging to all critical independent sets of a graph. SIAM J. Discret. Math. 26, 399–403 (2012)

    Article  Google Scholar 

  19. Levit, V.E., Mandrescu, E.: Critical independent sets and König-Egerváry graphs. Graphs Comb. 28, 243–250 (2012)

    Article  Google Scholar 

  20. Levit, V.E., Mandrescu, E.: Critical sets in bipartite graphs. Ann. Comb. 17, 543–548 (2013)

    Article  MathSciNet  Google Scholar 

  21. Levit, V.E., Mandrescu, E.: On the structure of the minimum critical independent set of a graph. Discret. Math. 313, 605–610 (2013)

    Article  MathSciNet  Google Scholar 

  22. Levit, V.E., Mandrescu, E.: Critical independent sets in a graph. In: 3rd International Conference on Discrete Mathematics, 10–14 June 2013, Karnatak University, Dharwad, India (2013)

    Google Scholar 

  23. Levit, V.E., Mandrescu, E.: A set and collection lemma. Electron. J. Comb. 21, #P1.40 (2014)

    Google Scholar 

  24. Levit, V.E., Mandrescu, E.: Critical independent sets of a graph. arXiv:1407.7368 [cs.DM], 15 p. (2014)

  25. Levit, V.E., Mandrescu, E.: Intersections and unions of critical independent sets in bipartite graphs. Bulletin mathématique de la Société des Sciences Mathématiques de Roumanie 57, 257–260 (2016)

    MathSciNet  MATH  Google Scholar 

  26. Levit, V.E., Mandrescu, E.: On König-Egerváry collections of maximum critical independent sets. Art Discret. Appl. Math. 2, #P1.02 (2019)

    Article  Google Scholar 

  27. Lorentzen, L.C.: Notes on covering of arcs by nodes in an undirected graph, Technical report ORC 66-16, Operations Research Center, University of California, Berkeley, California (1966)

    Google Scholar 

  28. Lovász, L., Plummer, M.D.: Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, Amsterdam (1986)

    Google Scholar 

  29. Schrijver, A.: Combinatorial Optimization. Springer, Berlin (2003)

    MATH  Google Scholar 

  30. Short, T.M.: KE Theory & the number of vertices belonging to all maximum independent sets in a graph, M.Sc. thesis, Virginia Commonwealth University (2011)

    Google Scholar 

  31. Short, T.M.: On some conjectures concerning critical independent sets of a graph. Electron. J. Comb. 23, #P2.43 (2016)

    Google Scholar 

  32. Sterboul, F.: A characterization of the graphs in which the transversal number equals the matching number. J. Comb. Theory B 27, 228–229 (1979)

    Article  MathSciNet  Google Scholar 

  33. Trukhanov, S.: Novel approaches for solving large-scale optimization problems on graphs, Ph.D. thesis, University of Texas (2008)

    Google Scholar 

  34. Zhang, C.Q.: Finding critical independent sets and critical vertex subsets are polynomial problems. SIAM J. Discret. Math. 3, 431–438 (1990)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgments

The first author would like to thank the organizers of the Mathematical Optimization Theory and Operations Research Conference - MOTOR2019 for an opportunity to deliver an invited lecture on critical independent sets.

Author information

Authors and Affiliations

  1. Ariel University, 40700, Ariel, Israel

    Vadim E. Levit

  2. Holon Institute of Technology, 5810201, Holon, Israel

    Eugen Mandrescu

Authors
  1. Vadim E. Levit
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Eugen Mandrescu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Vadim E. Levit .

Editor information

Editors and Affiliations

  1. Krasovsky Institute of Mathematics and Mechanics, Ekaterinburg, Russia

    Michael Khachay

  2. Sobolev Institute of Mathematics, Novosibirsk, Russia

    Yury Kochetov

  3. University of Florida, Gainesville, FL, USA

    Panos Pardalos

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Levit, V.E., Mandrescu, E. (2019). Critical and Maximum Independent Sets Revisited. In: Khachay, M., Kochetov, Y., Pardalos, P. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2019. Lecture Notes in Computer Science(), vol 11548. Springer, Cham. https://doi.org/10.1007/978-3-030-22629-9_1

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-22629-9_1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-22628-2

  • Online ISBN: 978-3-030-22629-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation