Geodesic
New Results Relating Independence and Matchings
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 921-935.

Voir la notice de l'article provenant de la source Library of Science

In this paper we study relationships between the matching number, written µ(G), and the independence number, written α(G). Our first main result is to show α(G) ≤ µ(G) + |X| − µ(G[NG[X]]), where X is any intersection of maximum independent sets in G. Our second main result is to show δ(G) α(G) ≤ Δ(G)µ(G), where δ(G) and Δ(G) denote the minimum and maximum vertex degrees of G, respectively. These results improve on and generalize known relations between µ(G) and α(G). Further, we also give examples showing these improvements.
Keywords: independent sets, independence number, matchings, matching number 
@article{DMGT_2022_42_3_a14,
     author = {Caro, Yair and Davila, Randy and Pepper, Ryan},
     title = {New {Results} {Relating} {Independence} and {Matchings}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {921--935},
     publisher = {mathdoc},
     volume = {42},
     number = {3},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a14/}
}
TY  - JOUR
AU  - Caro, Yair
AU  - Davila, Randy
AU  - Pepper, Ryan
TI  - New Results Relating Independence and Matchings
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 921
EP  - 935
VL  - 42
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a14/
LA  - en
ID  - DMGT_2022_42_3_a14
ER  - 
%0 Journal Article
%A Caro, Yair
%A Davila, Randy
%A Pepper, Ryan
%T New Results Relating Independence and Matchings
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 921-935
%V 42
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a14/
%G en
%F DMGT_2022_42_3_a14
Caro, Yair; Davila, Randy; Pepper, Ryan. New Results Relating Independence and Matchings. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 921-935. http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a14/

[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 preprint 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 α+-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 preprint 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).