DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

Y. Caro

Yair Caro

Department of MathematicsUniversity of Haifa- OranimTivon -36006,ISRAEL

email: yacaro@kvgeva.org.il

R. Davila

Randy Davila

University of Houston-Downtown

email: davilar@uhd.edu

R. Pepper

Ryan Pepper

University of Houston-Downtown, TX

email: pepperr@uhd.edu

Title:

New results relating inependence and matchings

PDF

Source:

Discussiones Mathematicae Graph Theory 42(3) (2022) 921-935

Received: 2019-10-05 , Revised: 2020-03-15 , Accepted: 2020-03-16 , Available online: 2020-04-20 , https://doi.org/10.7151/dmgt.2317

Abstract:

In this paper we study relationships between the matching number, written $\mu(G)$, and the independence number, written $\alpha(G)$. Our first main result is to show $$ \alpha(G) \le \mu(G) + |X| - \mu(G[N_G[X]]), $$ where $X$ is any intersection of maximum independent sets in $G$. Our second main result is to show $$ \delta(G)\alpha(G) \le \Delta(G)\mu(G), $$ where $\delta(G)$ and $\Delta(G)$ denote the minimum and maximum vertex degrees of $G$, respectively. These results improve on and generalize known relations between $\mu(G)$ and $\alpha(G)$. Further, we also give examples showing these improvements.

Keywords:

independent sets, independence number, matchings, matching number

References:

  1. F. Bonomo, M.C. Dourado, G. Durán, L. Faria, L.N. Grippo and M.D. Safe, Forbidden subgraphs and the König-Egerváry property, Discrete Appl. Math. 161 (2013) 2380–2388.
    https://doi.org/10.1016/J.DAM.2013.04.020
  2. E. Boros, M.C. Golumbic and V.E. Levit, On the number of vertices belonging to all maximum stable sets of a graph, Discrete Appl. Math. 124 (2002) 17–25.
    https://doi.org/10.1016/S0166-218X(01)00327-4
  3. B. Bollobás, Random Graphs (Cambridge University Press, 2011).
    https://doi.org/10.1017/CBO9780511814068
  4. J.M. Bourjolly and W.R. Pulleyblank, König-Egerváry graphs, $2$-bicritical graphs, and fractional matchings, Discrete Appl. Math. 24 (1989) 63–82.
    https://doi.org/10.1016/0166-218X(92)90273-D
  5. A. Coja-Oghlan and C. Efthymiou, On independent sets in random graphs, Random Structures Algorithms 47 (2015) 436–486.
    https://doi.org/10.1002/rsa.20550
  6. R. Davila, TxGraffiti.
    https://github.com/RandyRDavila/TNP-That-New-Program
  7. E. DeLaVina, Graffiti.pc.
    cms.uhd.edu/faculty/delavinae/research/Graffitipc.PDF
  8. Z. Deniz, V.E. Levit and E. Mandrescu, On graphs admitting two disjoint maximum independent sets (2019).
    arXiv: 1807.06914v2
  9. S. Fajtlowicz, Toward fully automated fragments of graph theory, preprint.
  10. A. Finbow, B. Hartnell and R.J. Nowakowski, A characterization of well covered graphs of girth $5$ or greater, J. Combin. Theory Ser. B 57 (1993) 44–68.
    https://doi.org/10.1006/jctb.1993.1005
  11. J.C. Fournier, Coloration des aretes dun graphe, Cahiers du CERO (Bruxelles) 15 (1973) 311–314.
  12. A. Frieze and B. Pittel, Perfect matchings in random graphs with prescribed minimal degree, Math. Comput. Sci. III (2004) 95–132.
    https://doi.org/10.1007/978-3-0348-7915-6_11
  13. W. Goddard and M.A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math. 313 (2013) 839–854.
    https://doi.org/10.1016/j.disc.2012.11.031
  14. P. Hall, On representation of subsets, J. Lond. Math. Soc. 10 (1935) 26–30.
    https://doi.org/10.1112/jlms/s1-10.37.26
  15. C.E. Larson and R. Pepper, Graphs with equal independence and annihilation numbers, Electron. J. Combin. 18 (2011) #P180.
    https://doi.org/10.37236/667
  16. C.E. Larson, The critical independence number and an independence decomposition, European J. Combin. 32 (2011) 294–300.
    https://doi.org/10.1016/j.ejc.2010.10.004
  17. V.E. Levit and E. Mandrescu, On $\alpha^{+}$- stable König-Egerváry graphs, Discrete Math. 263 (2003) 179–190.
    https://doi.org/10.1016/S0012-365X(02)00528-9
  18. V.E. Levit and E. Mandrescu, On maximum matchings in König-Egerváry graphs, Discrete Appl. Math. 161 (2013) 1635–1638.
    https://doi.org/10.1016/j.dam.2013.01.005
  19. V.E. Levit and E. Mandrescu, On the critical difference of almost bipartite graphs (2019).
    arXiv: 1905.09462v1
  20. G.L. Nemhauser and L.E. Trotter Jr., Vertex packings: Structural properties and algorithms, Math. Program. 8 (1975) 232–248.
    https://doi.org/10.1007/BF01580444
  21. R. Pepper, Binding Independence, Ph.D. Thesis (University of Houston, Houston, TX, 2004).
  22. M.D. Plummer, Well-covered graphs: A survey, Quaest. Math. 16 (1993) 253–287.
    https://doi.org/10.1080/16073606.1993.9631737
  23. J.C. Picard and M. Queyranne, On the integer-valued variables in the lonear vertex packing problem, Math. Program. 12 (1977) 97–101.
    https://doi.org/10.1007/BF01593772
  24. W.R. Pulleyblank, Minimum node covers and $2$-bicritical graphs, Math. Program. 17 (1979) 91–103.
    https://doi.org/10.1007/BF01588228
  25. B. Xu, On edge domination numbers of graphs, Discrete Math. 294 (2005) 311–316.
    https://doi.org/10.1016/j.disc.2004.11.008
  26. D.B. West, Introduction to Graph Theory, 2nd Edition (Prentice-Hall, 2000).

Close