Article in volume
Authors:
Title:
New results relating inependence and matchings
PDFSource:
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:
- 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 - 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 - B. Bollobás, Random Graphs (Cambridge University Press, 2011).
https://doi.org/10.1017/CBO9780511814068 - 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 - 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 - R. Davila, TxGraffiti.
https://github.com/RandyRDavila/TNP-That-New-Program - E. DeLaVina, Graffiti.pc.
cms.uhd.edu/faculty/delavinae/research/Graffitipc.PDF - Z. Deniz, V.E. Levit and E. Mandrescu, On graphs admitting two disjoint maximum independent sets (2019).
arXiv: 1807.06914v2 - S. Fajtlowicz, Toward fully automated fragments of graph theory, preprint.
- 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 - J.C. Fournier, Coloration des aretes dun graphe, Cahiers du CERO (Bruxelles) 15 (1973) 311–314.
- 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 - 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 - P. Hall, On representation of subsets, J. Lond. Math. Soc. 10 (1935) 26–30.
https://doi.org/10.1112/jlms/s1-10.37.26 - 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 - 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 - 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 - 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 - V.E. Levit and E. Mandrescu, On the critical difference of almost bipartite graphs (2019).
arXiv: 1905.09462v1 - 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 - R. Pepper, Binding Independence, Ph.D. Thesis (University of Houston, Houston, TX, 2004).
- M.D. Plummer, Well-covered graphs: A survey, Quaest. Math. 16 (1993) 253–287.
https://doi.org/10.1080/16073606.1993.9631737 - 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 - W.R. Pulleyblank, Minimum node covers and $2$-bicritical graphs, Math. Program. 17 (1979) 91–103.
https://doi.org/10.1007/BF01588228 - B. Xu, On edge domination numbers of graphs, Discrete Math. 294 (2005) 311–316.
https://doi.org/10.1016/j.disc.2004.11.008 - D.B. West, Introduction to Graph Theory, 2nd Edition (Prentice-Hall, 2000).
Close