Hostname: page-component-6bf8c574d5-t27h7 Total loading time: 0 Render date: 2025-02-16T18:50:36.797Z Has data issue: false hasContentIssue false
  • English
  • Français

Unified bounds for the independence number of graphs

Part of: Basic linear algebra Communication, information Graph theory

Published online by Cambridge University Press:  11 December 2023

Jiang Zhou
Jiang Zhou*
Affiliation:
College of Mathematical Sciences, Harbin Engineering University, Harbin, PR China
*
e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The Hoffman ratio bound, Lovász theta function, and Schrijver theta function are classical upper bounds for the independence number of graphs, which are useful in graph theory, extremal combinatorics, and information theory. By using generalized inverses and eigenvalues of graph matrices, we give bounds for independence sets and the independence number of graphs. Our bounds unify the Lovász theta function, Schrijver theta function, and Hoffman-type bounds, and we obtain the necessary and sufficient conditions of graphs attaining these bounds. Our work leads to some simple structural and spectral conditions for determining a maximum independent set, the independence number, the Shannon capacity, and the Lovász theta function of a graph.

Keywords

Independence numbergraph matrixLovász theta functionShannon capacitygeneralized inverseeigenvalue

MSC classification

Primary: 05C69: Dominating sets, independent sets, cliques 05C50: Graphs and linear algebra (matrices, eigenvalues, etc.) 94A15: Information theory, general 15A09: Matrix inversion, generalized inverses
Type
Article
Information
Canadian Journal of Mathematics , Volume 77 , Issue 1 , February 2025 , pp. 97 - 117
Check for updates
Copyright
© The Author(s), 2023. Published by Cambridge University Press on behalf of The Canadian Mathematical Society

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

This work is supported by the National Natural Science Foundation of China (Grant No. 12071097) and the Natural Science Foundation for The Excellent Youth Scholars of the Heilongjiang Province (Grant No. YQ2022A002).

References

Alon, N., The Shannon capacity of a union . Combinatorica 18(1998), 301–310.CrossRefGoogle Scholar
Ben-Israel, A. and Greville, T. N. E., Generalized inverses: Theory and applications, 2nd ed., Springer, New York, 2003.Google Scholar
Berman, A. and Zhang, X. D., On the spectral radius of graphs with cut vertices . J. Combin. Theory Ser. B 83(2001), 233–240.CrossRefGoogle Scholar
Bohman, T., A limit theorem for the Shannon capacities of odd cycles I . Proc. Amer. Math. Soc. 131(2003), 3559–3569.CrossRefGoogle Scholar
Brouwer, A. E. and Haemers, W. H., Spectra of graphs, Springer, New York, 2012.CrossRefGoogle Scholar
Chung, F. R. K. and Yau, S. T., Discrete Green’s functions . J. Combin. Theory Ser. A 91(2000), 191–214.CrossRefGoogle Scholar
Cvetković, D., Rowlinson, P., and Simić, S., An introduction to the theory of graph spectra, Cambridge University Press, Cambridge, 2010.Google Scholar
Delsarte, P., An algebraic approach to the association schemes of coding theory . Philips Res. Rep. Suppl. 10(1973), vi+97.Google Scholar
Ellis, D., Filmus, Y., and Friedgut, E., Triangle-intersecting families of graphs . J. Eur. Math. Soc. 14(2012), 841–885.CrossRefGoogle Scholar
Ellis, D., Friedgut, E., and Pilpel, H., Intersecting families of permutations . J. Amer. Math. Soc. 24(2011), 649–682.CrossRefGoogle Scholar
Erdös, P., Ko, C., and Rado, R., Intersection theorems for systems of finite sets . Quart. J. Math. Oxford Ser. 12(1961), 313–320.CrossRefGoogle Scholar
Frankl, P. and Wilson, R. M., The Erdös–Ko–Rado theorem for vector spaces . J. Combin. Theory Ser. A 43(1986), 228–236.CrossRefGoogle Scholar
Friedgut, E., On the measure of intersecting families, uniqueness and stability . Combinatorica 28(2008), 503–528.CrossRefGoogle Scholar
Godsil, C. D. and Newman, M. W., Eigenvalue bounds for independent sets . J. Combin. Theory Ser. B 98(2008), 721–734.CrossRefGoogle Scholar
Godsil, C. D. and Royle, G., Algebraic graph theory, Springer, New York, 2001.CrossRefGoogle Scholar
Haemers, W. H., On some problems of Lovász concerning the Shannon capacity of a graph . IEEE Trans. Inform. Theory 25(1979), 231–232.CrossRefGoogle Scholar
Haemers, W. H., Eigenvalue techniques in design and graph theory. Ph.D. thesis, Technical University Eindhoven, 1979, Mathematical Centre Tracts, 121, Amsterdam, 1980.Google Scholar
Harant, J. and Richter, S., A new eigenvalue bound for independent sets . Discrete Math. 338(2015), 1763–1765.CrossRefGoogle Scholar
Lovász, L., On the Shannon capacity of a graph . IEEE Trans. Inform. Theory 25(1979), 1–7.CrossRefGoogle Scholar
Lu, M., Liu, H., and Tian, F., Laplacian spectral bounds for clique and independence numbers of graphs . J. Combin. Theory Ser. B 97(2007), 726–732.CrossRefGoogle Scholar
Polak, S. C. and Schrijver, A., New lower bound on the Shannon capacity of ${C}_7$ from circular graphs. Inform. Process. Lett. 143(2019), 37–40.CrossRefGoogle Scholar
Schrijver, A., A comparison of the Delsarte and Lovász bounds . IEEE Trans. Inform. Theory 25(1979), 425–429.CrossRefGoogle Scholar
Shannon, C. E., The zero-error capacity of a noisy channel . IRE Trans. Inform. Theory 2(1956), 8–19.CrossRefGoogle Scholar
Spielman, D. A., Graphs, vectors, and matrices . Bull. Amer. Math. Soc. 54(2017), 45–61.CrossRefGoogle Scholar
Zhou, J. and Bu, C., Eigenvalues and clique partitions of graphs . Adv. Appl. Math. 129(2021), 102220.CrossRefGoogle Scholar