Independent sets in graphs

A. B. Dainiak ; A. A. Sapozhenko

Diskretnaya Matematika, Tome 28 (2016) no. 1, pp. 44-77.

Résumé

We give a survey of the enumeration of independent sets in graphs and of some related problems.

Détail

Keywords: independent sets, domination, enumeration, extremal graph theory.

Bibliographie

[1] Alekseev V. E., “Verkhnyaya otsenka chisla maksimalnykh nezavisimykh mnozhestv grafa”, Diskretnaya matematika, 19:3 (2007), 84–88 | DOI | MR | Zbl

[2] Voronin V. P., Demakova E. V., “O chisle nezavisimykh mnozhestv dlya nekotorykh semeistv grafov”, Trudy 4-i mezhdunar. konf. «Diskretnye modeli v teorii upravlyayuschikh sistem», Krasnovidovo, 19-25 iyunya 2000 g., MAKSPress, Moskva, 145–149

[3] Garey M.R., Johnson D.S., Computers and Intractability. A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979, 347 pp. ; Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, Moskva, 1982 | MR | Zbl | MR

[4] Dainyak A. B., Kurnosov A. D., “Ob odnoi ekstremalnoi obratnoi zadache teorii grafov”, Diskretnyi analiz i issledovanie operatsii, 22:1 (2015), 17–29 | MR

[5] Dainyak A. B., “O chisle nezavisimykh mnozhestv v grafakh s fiksirovannym chislom nezavisimosti”, Diskretnaya matematika, 19:2 (2007), 63–66 | DOI | MR | Zbl

[6] Dainyak A. B., “O chisle nezavisimykh mnozhestv v polnykh $q$-arnykh derevyakh”, Uchenye zapiski Kazanskogo gos. un-ta, 151:2 (2009), 59–64 | MR | Zbl

[7] Dainyak A. B., “Otsenki chisla nezavisimykh mnozhestv v grafakh s fiksirovannym chislom nezavisimosti”, Vestnik Mosk. un-ta, ser. 15. Vychisl. matem. i kibern., 2009, no. 2, 45–48 | MR

[8] Dmitriev A. S., Edinstvennost ekstremalnogo grafa v zadache o maksimalnom kolichestve nezavisimykh mnozhestv v regulyarnykh grafakh, arXiv:1602.08736

[9] Zykov A. A., “O nekotorykh svoistvakh lineinykh kompleksov”, Mat. sb., 24:2 (1949), 163–188 | MR | Zbl

[10] Kolchin V.F., Sluchainye grafy, 2-e izd., Fizmatlit, Moskva, 2004; Kolchin V.F., Random Graphs, Cambridge University Press, 1998, 268 pp. | MR

[11] Korshunov A. D., Sapozhenko A. A., “O chisle dvoichnykh kodov s rasstoyaniem 2”, Problemy kibernetiki. Vyp. 40., Nauka, Moskva, 1993, 111–140

[12] Omelyanov K. G., O chisle mnozhestv, svobodnykh ot summ, kand. diss., Moskva, 2006

[13] Omelyanov K. G., “O chisle nezavisimykh mnozhestv v povrezhdennykh grafakh Keli”, Diskretnaya matematika, 17:3 (2005), 105–108 | DOI | MR | Zbl

[14] Sapozhenko A. A., “Verkhnyaya otsenka chisla nezavisimykh mnozhestv v grafakh”, Doklady RAN, 373:4 (2007), 467–470

[15] Sapozhenko A. A., “O chisle nezavisimykh mnozhestv v grafakh”, Sb. trudov XIII mezhdunar. konf. «Problemy teoreticheskoi kibernetiki», Kazanskii gos. universitet, Kazan, 2002, 89–93

[16] Sapozhenko A. A., “O chisle nezavisimykh mnozhestv v grafakh”, Vestnik Mosk. un-ta, ser. 1, Matem., mekh., 2004, no. 3, 1–13 | MR

[17] Sapozhenko A. A., “O chisle nezavisimykh mnozhestv v rasshiritelyakh”, Diskretnaya matematika, 13:1 (2001), 56–62 | DOI | MR | Zbl

[18] Abello J., Butenko S., Pardalos P. M., Resende M. G. C., “Finding independent sets in a graph using continuous multivariable polynomial formulations”, J. Global Optimiz., 21:2 (2001), 111–137 | DOI | MR | Zbl

[19] Ajtai M., Komlos J., Szemeredi E., “a note on Ramsey numbers”, J. Comb. Theory Ser. A, 29 (1980), 354–360 | DOI | MR | Zbl

[20] Alavi Y., Erdős P., Malde P., Schwenk A., “The vertex independence sequence of a graph is not constrained”, Congr. Numer., 58 (1987), 15–23 | MR | Zbl

[21] Alekseev V. E., Lozin V. V., “Augmenting graphs for independent sets”, Discr. Appl. Math., 145:1 (2004), 3–10 | DOI | MR | Zbl

[22] Alekseev V. E., Lozin V. V., “Independent sets of maximum weight in (p,q)-colorable graphs”, Discr. Math., 265:1-3 (2003), 351–356 | DOI | MR | Zbl

[23] Alekseev V. E. Polynomial algorithm for finding the largest independent sets in graphs without forks, Discr. Appl. Math., 135:1-3 (2004), 3–16 | DOI | MR

[24] Alexander J., Cutler J., Mink T., “Independent sets in graphs with given minimum degree”, Electr. J. Comb., 19:3 (2012), #P37 | MR | Zbl

[25] Alon N., Balogh J., Morris R., Samotij W., “Counting sum-free sets in abelian groups”, Israel J. Math., 199:1 (2014), 309–344 | DOI | MR | Zbl

[26] Alon N., Lubetzky E., “The Shannon capacity of a graph and the independence numbers of its powers”, IEEE Trans. Inf. Th., 52 (2006), 2172–2176 | DOI | MR | Zbl

[27] Alon N., Spencer J. H., The Probabilistic Method, 3rd Edition, Wiley, New York, 2008, 376 pp. | MR

[28] Alon N., “Independence numbers of locally sparse graphs and a Ramsey type problem”, Random Struct. and Algor., 9:3 (1996), 271–278 | 3.0.CO;2-U class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[29] Alon N., “Independent sets in regular graphs and Sum-Free Subsets of Finite Groups”, Israel J. Math., 73:2 (1991), 247–256 | DOI | MR | Zbl

[30] Alon N., “The Shannon capacity of a union”, Combinatorica, 18 (1998), 301–310 | DOI | MR | Zbl

[31] Aouchiche M., Brinkmann G., Hansen P., “Variable neighborhood search for extremal graphs. 21. Conjectures and results about the independence number”, Discr. Appl. Math., 156 (2008), 2530–2542 | DOI | MR | Zbl

[32] Balas E., Yu Ch. S., “On graphs with polynomially solvable maximum-weight clique problem”, Networks, 19 (1989), 247–253 | DOI | MR | Zbl

[33] Baumert L., McEliece R., Rodemich E., Rumsey H., Stanley R., Taylor H., “A combinatorial packing problem”, Computers in Algebra and Number Theory, American Mathematical Society, Providence, RI, 1971, 97–108 | MR | Zbl

[34] Blidia M., Chellali M., Favaron O., Meddaha N., “On $k$-independence in graphs with emphasis on trees”, Discr. Math., 307 (2007), 2209–2216 | DOI | MR | Zbl

[35] Bohman T., Holzman R., “A nontrivial lower bound on the Shannon capacities of the complements of odd cycles”, IEEE Trans. Inf. Th., 49 (2003), 721–722 | DOI | MR | Zbl

[36] Bohman T., Ruszinko M., Thoma L., “Shannon capacity of large odd cycles”, Proc. 2000 IEEE Intern. Symp. Inf. Th., IEEE, Sorrento, 2000, 179 | DOI

[37] Bohman T., “A limit theorem for the Shannon capacities of odd cycles II”, Proc. Amer. Math. Soc., 133 (2005), 537–543 | DOI | MR | Zbl

[38] Bohman T., “A limit theorem for the Shannon capacities of odd cycles I”, Proc. Amer. Math. Soc., 131 (2003), 3559–3569 | DOI | MR | Zbl

[39] Bollobás B., Erdős P., “Cliques in random graphs”, Math. Proc. Camb. Phil. Soc., 80:3 (1976), 419–427 | DOI | MR | Zbl

[40] Bollobás B., Extremal Graph Theory, Academic Press, 1978 | MR | Zbl

[41] Bollobás B., Random graphs, 2nd edition, Cambridge Univ. Press, 2001 | MR

[42] Bollobás B., “The independence ratio of regular graphs”, Proc. AMS, 83:2 (1981), 433–436 | DOI | MR | Zbl

[43] Borgs C., Chayes J., Lovász L., Sós V. T., Vesztergombi K., “Counting graph homomorphisms”, Topics in Discrete Mathematics. Algorithms and Combinatorics Volume 26, 2006, 315–371 | MR | Zbl

[44] Borowiecki M., Michalak D., “Generalized independence and domination in graphs”, Discr. Math., 191:1–3 (1998), 51–56 | DOI | MR | Zbl

[45] Broersma H., Kloks T., Kratsch D., Muller H., “Independent sets in asteroidal triple-free graphs”, Lect. Notes Comput. Sci. Vol. 1256 Proc. 24-th Intern. Colloq. on Automata, Languages and Programming, Springer, 760–770 | MR

[46] Bruyére V., Mélot H., “Turán graphs, stability number, and Fibonacci index”, B. Yang, D.-Z. Du, and C.A. Wang (Eds.): Combinatorial Optimization and Applications: Second International Conference, COCOA 2008, LNCS 5165, 2008, 127–138 | Zbl

[47] Buló S., Pelillo M., “New bounds on the clique number of graphs based on spectral hypergraph theory”, Lect. Notes Comput. Sci. Vol. 5851. Learning and Intelligent Optimization, Springer, 2009, 45–58

[48] Butenko S., Pardalos P., Sergienko I., Shylo V., Stetsyuk P., “Finding maximum independent sets in graphs arising from coding theory”, Proc. 2002 ACM Symp. Appl. Computing, ACM, 542–546

[49] Byskov J. M., “Enumerating maximal independent sets with applications to graph colouring”, Oper. Res. Lett., 32 (2004), 547–556 | DOI | MR | Zbl

[50] Calkin N. J., Wilf H. S., “The number of independent sets in a grid graph”, SIAM J. Discr. Math., 11:1 (1998), 54–60 | DOI | MR | Zbl

[51] Caragiannis I., Fishkin A. V., Kaklamanis C., Papaioannou E., “Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs”, Discr. Appl. Math., 155:2 (2007), 119–136 | DOI | MR | Zbl

[52] Caro Y., Hansberg A., “New approach to the $k$-independence number of a graph”, Electr. J. Comb., 20:1 (2013), #P33 | MR | Zbl

[53] Caro Y., New results on the independence number, Technical Report, Tel Aviv University, 1979

[54] Carroll T., Galvin D., Tetali P., “Matchings and independent sets of a fixed size in regular graphs”, J. Comb. Th., Ser. A, 116:7 (2009), 1219–1227 | DOI | MR | Zbl

[55] Chang G. J., Jou M.-J., “The number of maximal independent sets in connected triangle-free graphs”, Discr. Math., 197/198 (1999), 169–178 | DOI | MR | Zbl

[56] Codenotti B., Gerace I., Resta G., “Some remarks on the Shannon capacity of odd cycles”, Ars Combinatoria, 66 (2003), 243–258 | MR

[57] Cohen D., “Counting stable sets in trees”, Seminaire Lotharingien de Combinatoire, 10eme session, R. König, ed., Institute de Recherche Mathématique Avancée Pub., Strasbourg, France, 1984, 48–52

[58] Coja-Oghlan A., “Finding large independent sets in polynomial expected time”, Lect. Notes Comput. Sci. Vol. 2607. Proc. 20th Annual Symp. on Theoretical Aspects of Comput. Sci., Springer, 2003, 511–522 | MR | Zbl

[59] Croitoru C., “On stables in graphs”, Proc. Third Coll. Operations Research, Babes-Bolyai University, Cluj-Napoca, Romania, 1979, 55–60 | MR | Zbl

[60] Cutler J., Radcliffe A. J., “Extremal problems for independent set enumeration”, Electr. J. Comb., 18 (2011), #P169 | MR | Zbl

[61] Cutler J., Radcliffe A. J., “The maximum number of complete subgraphs in a graph with given maximum degree”, J. Comb. Th., Ser. B, 104 (2013), 60–71 | DOI | MR

[62] D. E. Knuth, “The sandwich theorem”, Electron. J. Comb., 1 (1994), #A1 | MR | Zbl

[63] Dahllöf V., Jonsson P., “An algorithm for counting maximum weighted independent sets and its applications”, Proc. 2002 ACM Symp. Appl. Computing, 542–546

[64] Dainiak A. B., Sharp bounds for the number of maximal independent sets in trees of fixed diameter, arXiv:0812.4948v1, 2008

[65] Dainyak A. B., “On the number of independent sets in the trees of a fixed diameter”, J. Appl. and Industrial Math., 4:2 (2010), 163–171 | DOI | MR

[66] Davies E., Jenssen M., Perkins W., Roberts B., Independent sets, matchings, and occupancy fractions, arXiv:1508.04675

[67] Demange M., “A note on the approximation of a minimum-weight maximal independent set”, Comput. Optimiz. and Appl., 14:1 (1999), 157–169 | DOI | MR | Zbl

[68] Derikvand T., Oboudi M. R., “On the number of maximum independent sets of graphs”, Transactions on Combinatorics, 3:1 (2014), 29–36 | MR

[69] Diestel R., Graph theory. 2nd edition, (Imeetsya perevod: Distel R., Teoriya grafov // Novosibirsk, IM SO RAN, 2002, 336.), Springer-Verlag, 2000 | MR

[70] Duckworth W., Wormald N. C., “On the independent domination number of random regular graphs”, Comb., Prob. and Comput., 15:4 (2006), 513–522 | DOI | MR | Zbl

[71] Duckworth W., “Maximum 2-independent sets of random cubic graphs”, Australasian J. Comb., 27 (2003), 63–79 | MR | Zbl

[72] Duffus D., Frankl P., Rödl V., “Maximal independent sets in the covering graph of the cube”, Discr. Appl. Math., 161 (2013), 1203–1208 | DOI | MR | Zbl

[73] Dutton R., Chandrasekharan N., Brigham R., “On the number of independent sets of nodes in a tree”, Fibonacci Quart., 31:2 (1993), 98–104 | MR | Zbl

[74] Eckhoff J., “A new Turán-type theorem for cliques in graphs”, Discr. Math., 282 (2004), 113–122 | DOI | MR | Zbl

[75] Engel K., “On the Fibonacci number of an $m\times n$ lattice”, Fibonacci Quart., 28 (1990), 72–78 | MR | Zbl

[76] Eppstein D., “All maximal independent sets and dynamic dominance for sparse graphs”, Proc. 16th Annual ACM-SIAM Symp. Discr. Algor., ACM, 451–459 | MR | Zbl

[77] Erdős P., “On the graph-theorem of Paul Turán (In Hungarian)”, Mat. Lapok, 21 (1970), 249–251 | MR

[78] Erdős P., “On the number of complete subgraphs and circuits contained in graphs”, Cas. Pestováni Mat., 94 (1969), 290–296 | MR | Zbl

[79] Erdős P., “On the number of complete subgraphs contained in certain graphs”, Publ. Math. Inst. Hung. Acad. Sci., Ser. A, 7 (1962), 459–464 | MR | Zbl

[80] Farber M., Hujter M., Tuza Z., “An upper bound on the number of cliques in a graph”, Networks, 23 (1993), 207–210 | DOI | MR | Zbl

[81] Fink J. F., Jacobson M. S., “$n$-Domination in graphs”, Graph Theory with Applications to Algorithms and Computer Science, Wiley, New York, 1985, 283-300 | MR

[82] Finner H., “A generalization of Hölder’s inequality and some probability inequalities”, Ann. Probab., 20:4 (1992), 1893-–1901 | DOI | MR | Zbl

[83] Fomin F. V., Grandoni F., Kratsch D., “Measure and conquer: a simple $O(2^0.288n)$ independent set algorithm”, Proc. 17th Annual ACM-SIAM Symp. Discr. Algor., ACM, 2006, 18–25 | MR | Zbl

[84] Frendrup A., Pedersen A. S., Sapozhenko A. A., Vestergaard P. D., “Merrifield–Simmons index and minimum number of independent sets in short trees”, Ars Combinatoria, CXI (2013), 97–106 | MR

[85] Frieze A., Karoński M., Introduction to Random Graphs, Cambridge Univ. Press, 2015

[86] Füredi Z., “The number of maximal independent sets in connected graphs”, J. Graph Theory, 11 (1987), 463–470 | DOI | MR

[87] Galvin D., Zhao Y., “The number of independent sets in a graph with small maximum degree”, Graphs and Combinatorics, 27:2 (2011), 177–186 | DOI | MR | Zbl

[88] Galvin D., “Two problems on independent sets in graphs”, Discr. Math., 311:20 (2011), 2105–2112 | DOI | MR | Zbl

[89] Gan W., Loh P. S., Sudakov B., “Maximizing the number of independent sets of a fixed size”, Combinatorics, Probability and Computing / FirstView Article DOI: http://dx.doi.org/10.1017/S0963548314000546, 2014 | MR

[90] Gfeller B., Vicari E., “Graph algorithms: A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs”, Proc. 26th Annual ACM Symp. Princ. Distrib. Comput., ACM, 2007, 53–60 | Zbl

[91] Goddard W., Henning M. A., “Independent domination in graphs: a survey and recent results”, Discr. Math., 313 (2013), 839–854 | DOI | MR | Zbl

[92] Godsil C. D., Newman M. W., “Eigenvalue bounds for independent sets”, J. Comb. Th., Ser. B, 98 (2008), 721–734 | DOI | MR | Zbl

[93] Goldman D., Istrail S., Lancia G., Piccolboni A., Walenz B., “Algorithmic strategies in combinatorial chemistry”, Proc. 11th Annual ACM-SIAM Symp. Discr. Algor., ACM, 2000, 275–284 | MR | Zbl

[94] Griggs J. R., Grinstead C. M., Guichard D. R., “The number of maximal independent sets in a connected graph”, Discr. Math., 68 (1988), 211–220 | DOI | MR | Zbl

[95] Griggs J. R., “Lower bounds on the independence number in terms of the degrees”, J. Comb. Th., Ser. B, 34:1 (1983), 22–39 | DOI | MR | Zbl

[96] Gutman I., Harary F., “Generalizations of the matching polynomial”, Utilitas Mathematica, 24 (1983), 97–106 | MR | Zbl

[97] Gvozdenovič N., Laurent M., “Semidefinite bounds for the stability number of a graph via sums of squares of polynomials”, Math. Program., Ser. B, 110 (2007), 145–173 | DOI | MR | Zbl

[98] Hadziivanov N. G., “A generalization of Turán’s theorem on graphs”, C. R. Acad. Bulgare Sci., 29:11 (1976), 1567–1570 | MR | Zbl

[99] Haemert W., “On some problems of Lovász concerning the Shannon capacity of graphs”, IEEE Trans. Inf. Th., 25 (1979), 231–232 | DOI | MR

[100] Halldersson M. M., Radhakrishnan J., “Improved approximations of independent sets in bounded-degree graphs via subgraph removal”, Nordic J. Comput., 1:4 (1994), 475–492 | MR

[101] Harant J., Pruchnewski A., Voigt M., “On dominating sets and independent sets of graphs”, Combinatorics, Probability and Computing, 11 (1993), 1–10 | MR

[102] Harant J., Pruchnewski A., Voigt M., “On dominating sets and independent sets of graphs”, Comb., Prob. and Comput., 8:6 (1999), 547–553 | DOI | MR | Zbl

[103] Harary F., Graph theory, Addison-Wesley, 1969 | MR | Zbl

[104] Hayes T., Vigoda E., “Coupling with the stationary distribution and improved sampling for colorings and independent sets”, Proc. 16th Annual ACM-SIAM Symp. Discr. Algor., ACM, 2005, 971–979 | MR | Zbl

[105] Heckman C. C., Thomas R., “A new proof of the independence ratio of triangle-free cubic graphs”, Discr. Math., 233 (2001), 233–237 | DOI | MR | Zbl

[106] Heckman C. C., Thomas R., “Independent sets in triangle-free cubic planar graphs”, J. Comb. Th., Ser. B, 96:2 (2006), 253–275 | DOI | MR | Zbl

[107] Hedman B., “Another extremal problem for Turán graphs”, Discr. Math., 65:2 (1987), 173–176 | DOI | MR | Zbl

[108] Hedman B., “The maximum number of cliques in dense graphs”, Discr. Math., 54:2 (1985), 161–166 | DOI | MR | Zbl

[109] Hopkins G., Staton W., “Graphs with unique maximum independent sets”, Discr. Math., 57 (1985), 245–251 | DOI | MR | Zbl

[110] Hosoya H., “Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons”, Bull. Chem. Soc. Jpn., 44:9 (1971), 2332–2339 | DOI

[111] Hota M., Pal M., Pal T. K., “An efficient algorithm for finding a maximum weight $k$-independent set on trapezoid graphs”, Computational Optimization and Applications,, 18:1 (2001), 49–62 | DOI | MR | Zbl

[112] Hsu W.-L., “The coloring and maximum independent set problems on planar perfect graphs”, JACM, 35:3 (1988), 535–563 | DOI | MR

[113] Hua H., “A sharp upper bound for the number of stable sets in graphs with given number of cut edges”, Appl. Math. Lett., 22 (2009), 1380–1385 | DOI | MR | Zbl

[114] Huang Z., Chen S., Deng H., Wan X., “The Merrifield–Simmons Index of Acyclic Molecular Graphs”, MATCH Commun. Math. Comput. Chem., 66 (2011), 825–836 | MR | Zbl

[115] Hujter M., Tuza Ž., “The number of maximal independent sets in triangle-free graphs”, SIAM J. Discr. Math., 6:2 (1993), 284–288 | DOI | MR | Zbl

[116] Janson S., Luczak T., Rucinski A., Random Graphs, Wiley, New York, 2000 | MR | Zbl

[117] Jin Z., Li X., “Graphs with the second largest number of maximal independent sets”, Discr. Math., 308 (2008), 5864–5870 | DOI | MR | Zbl

[118] Jin Z., Yan S. H. F., “The second largest number of maximal independent sets in graphs with at most $k$ cycles”, Taiwanese J. Math., 13:5 (2009), 1397–1410 | MR | Zbl

[119] Jou M. J., Chang G. J., “Survey on counting maximal independent sets”, Proceedings of the Second Asian Mathematical Conference 1995 (Nakhon Ratchasima), World Sci. Publ., River Edge, N. J.,, 1998, 265–275 | MR | Zbl

[120] Jou M.-J., Chang G. J., Lin Chiang C., Ma T.-H., “A finiteness theorem for maximal independent sets”, J. Graphs and Combinatorics, 1996. | MR

[121] Jou M.-J., Chang G. J., “Maximal independent sets in graphs with at most one cycle”, Discr. Appl. Math, 79:1-3 (1997), 67–73 | DOI | MR | Zbl

[122] Jou M.-J., Chang G. J., “The number of maximum independent sets in graphs”, Taiwanese J. Math., 4:4 (2000), 685–695 | MR | Zbl

[123] Jou M.-J., Lin J.-J., “Trees with the second largest number of maximal independent sets”, Discr. Math., 309 (2009), 4469–4474 | DOI | MR | Zbl

[124] Jou M.-J., “The second largest number of maximal independent sets in connected graphs with at most one cycle”, J Comb Optim, 24 (2012), 192–201 | DOI | MR | Zbl

[125] Kahn J., “An entropy aproach to the hard-core model on bipartite graph”, Comb., Prob. and Comput., 10:3 (2001), 219–238 | DOI | MR

[126] Karp R. M., Wigderson A., “A fast parallel algorithm for the maximal independent set problem”, JACM, 32:4 (1985), 762–773 | DOI | MR | Zbl

[127] Kim J. H., “The Ramsey number $R(3,t)$ has order of magnitude $t^2/\log t$”, Random Struct. and Algor., 7 (1995), 173–207 | DOI | MR | Zbl

[128] Kirschenhofer P., Prodinger H., Tichy R. F., “Fibonacci numbers of graphs III”, Proceedings of the First International Conference on Fibonacci Numbers and Applications, 1986, 105–120 | MR | Zbl

[129] Kirschenhofer P., Prodinger H., Tichy R. F., “Fibonacci numbers of graphs II”, Fibonacci Quart., 21 (1983), 219–229 | MR | Zbl

[130] Koh K. M., Goh C. Y., Dong F. M., “The maximum number of maximal independent sets in unicyclic connected graphs”, Discr. Math., 308 (2008), 3761–3769 | DOI | MR | Zbl

[131] Lama P. C. B., Shiu W. C., Sun L., “On independent domination number of regular graphs”, Discr. Math., 202 (1999), 135–144 | DOI | MR

[132] Lauer J., Wormald N., “Large independent sets in regular graphs of large girth”, J. Comb. Th. Ser. B, 97:6 (2007), 999–1009 | DOI | MR | Zbl

[133] Law H. F., “On the number of independent sets in a tree”, Electr. J. Comb., 17 (2010), #N18 | MR | Zbl

[134] Levit V. E., Mandrescu E., Proceedings of the 1st International Conference on Algebraic Informatics, Aristotle Univ. Thessaloniki, Thessaloniki, 2005 | MR

[135] Levit V., Mandrescu E., “Partial unimodality for independence polynomials of König-Egerváry graphs”, Congr. Numer., 179 (2006) | MR | Zbl

[136] Li S., Zhang H., Zhang X., “Maximal independent sets in bipartite graphs with at least one cycle”, Discrete Mathematics and Theoretical Computer Science, 15:2 (2013), 243–258 | MR | Zbl

[137] Li Yu., Zhang Zh., “A note on eigenvalue bounds for independence numbers of non-regular graphs”, Discr. Appl. Math., 174 (2014), 146–149 | DOI | MR | Zbl

[138] Linek V., “Bipartite graphs can have any number of independent sets”, Discr. Math., 76:2 (1989), 131–136 | DOI | MR | Zbl

[139] Liu J., “Constraints on the number of maximal independent sets in graphs”, J. Graph Th., 18:2 (1994), 195–204 | DOI | MR | Zbl

[140] Liu J., “Maximal independent sets in bipartite graphs”, J. Graph Th., 17:4 (1993), 495–507 | DOI | MR | Zbl

[141] Lovász L., “On Shannon capacity of a graph”, IEEE Trans. Inf. Th., 25 (1979), 1–7 | DOI | MR | Zbl

[142] Lozin V. V., Milani M., “A polynomial algorithm to find an independent set of maximum weight in a fork-free graph”, Proc. 17th Annual ACM-SIAM Symp. Discr. Algor., ACM, 2006, 26–30 | MR | Zbl

[143] Lozin V. V., Mosca R., “Independent sets in extensions of $2K_2$-free graphs”, Discr. Appl. Math., 146:1 (2005), 74–80 | DOI | MR | Zbl

[144] Lubetzky E., Zhao Y., “On replica symmetry of large deviations in random graphs”, Random Struct. and Algor., 47:1, 109–-146 | DOI | MR | Zbl

[145] Luczak T., “A note on the sharp concentration of the chromatic number of random graph”, Combinatorica, 11:3 (1991), 287–310 | DOI | MR

[146] Mader W., “Homomorphieeigenschaften und mittlere Kantendichte von Graphen”, Math. Ann., 174 (1967), 265–268 | DOI | MR | Zbl

[147] Madiman M., Tetali P., “Information inequalities for joint distributions, with interpretations and applications”, IEEE Trans. Inf. Th., 56:6 (2010), 2699–2713 | DOI | MR

[148] Mathew K. A., Östergård P. R. J., New lower bounds for the Shannon capacity of odd cycles, 2015, arXiv: 1504.01472v1

[149] Matula D. W., “On the complete subgraphs of a random graph”, Combinatory Mathematics and its Applications, Chapel Hill, 1970, 356–369 | MR | Zbl

[150] Matula D., Beck L., “Smallest-last ordering and clustering and graph coloring algorithms”, J. ACM, 30 (1983), 417–427 | DOI | MR | Zbl

[151] Meir A., Moon J. W., “On maximal independent sets of nodes in trees”, J. Graph Th., 12:2 (1988), 265–283 | DOI | MR | Zbl

[152] Meir A., Moon J. W., “Relations between packing and covering numbers of a tree”, Pacific J. Math., 61:1 (1975), 225–233 | DOI | MR | Zbl

[153] Merrifield R. E., Simmons H. E., Topological methods in chemistry, Wiley, New York, 1989

[154] Miller R. E., Muller D. E., The problem of maximum consistent subsets, IBM Research Report RC-240. J. T. Watson Research Center, Yorktown Heights, N.Y., 1960

[155] Moon J. V., Mozer L., “On cliques in graphs”, Israel J. Math., 3 (1965), 23–28 | DOI | MR | Zbl

[156] Moscibroda T., Wattenhofer R., “Maximal independent sets in radio networks”, Proc. 24th Annual ACM Symp. Princ. Distrib. Comput., ACM, 2005, 148–157 | Zbl

[157] Motzkin T. S., Straus E. G., “Maxima for graphs and a new proof of a theorem of Turán”, Canad. J. Math., 17 (1965), 533–540 | DOI | MR | Zbl

[158] Nikiforov V., “More spectral bounds on the clique and independence numbers”, J. Comb. Th., Ser. B, 99 (2009), 819–826 | DOI | MR | Zbl

[159] Olejar D., Toman E., “On the order and the number of cliques in a random graph”, Math. Slovaca, 47:5 (1997), 499–510 | MR | Zbl

[160] Ostergard P. R. J., “Constructing combinatorial objects via cliques”, Webb. B.S. (ed.) Surveys in Combinatorics. London Mathematical Society Lecture Note Series, vol. 327., Cambridge Univ. Press, Cambridge, 2005, 57–82 | MR | Zbl

[161] Pedersen A. S., Vestergaard P. D., “An upper bound on the number of independent sets in a tree”, Ars Combinatoria, 84 (2007), 85–96 | MR | Zbl

[162] Pedersen A. S., Vestergaard P. D., “Bounds on the number of vertex independent sets in a graph”, Taiwanese J. Math., 10 (2006), 1575–1587 | MR | Zbl

[163] Pedersen A. S., Vestergaard P. D., “The number of independent sets in unicyclic graphs”, Discr. Appl. Math., 152:1-3 (2005), 246–256 | DOI | MR | Zbl

[164] Prodinger H., Tichy R. F., “Fibonacci numbers of graphs”, Fibonacci Quart., 19 (1982), 16–21 | MR

[165] Roman S., “The maximum number of $q$-cliques in a graph with no $p$-clique”, Discr. Math., 14 (1976), 365–370 | DOI | MR

[166] Rosenfeld M., “Independent sets in regular graphs”, Israel J. Math., 2:4 (1964), 262–272 | DOI | MR | Zbl

[167] Sagan B. E., Vatter V. R., “Maximal and maximum independent sets in graphs with at most $r$ cycles”, J. Graph Th., 53:4 (2006), 283–314 | DOI | MR | Zbl

[168] Sagan B. E., “A note on independent sets in trees”, SIAM J. Discr. Math., 1 (1988), 105–108 | DOI | MR | Zbl

[169] Sapozhenko A. A., On the number of independent sets in bipartite graphs with large minimum degree, DIMACS Technical Report 2000-25

[170] Sapozhenko A. A., “Independent sets in quasi-regular graphs”, European J. Comb., 27 (2006), 1206–1210 | DOI | MR | Zbl

[171] Sapozhenko A. A., “Systems of containers and enumeration problems”, Lect. Notes Comput. Sci. Vol 3777. Proceedings 3rd Intern. Symp. SAGA 2005, Springer, 2005, 1–13 | Zbl

[172] Sauer N., “A generalization of a theorem of Turán”, J. Combinatorial Theory Ser. B, 1971, 109–112 | DOI | MR | Zbl

[173] Shachnai H., Srinivasan A., “Maximal independent sets in graphs and hypergraphs”, SIAM J. on Discr. Math., 18:3 (2005), 488–500 | DOI | MR

[174] Shannon C. E., “The zero-error capacity of a noisy channel”, IRE Transactions on Information Theory, IT-2:3 (1956), 8–19 | DOI | MR

[175] Shearer J. B., “On the independence number of sparse graphs”, Random Struct. and Algor., 7 (1995), 269–271 | DOI | MR | Zbl

[176] Slater P. J.\, “The Hedetniemi number of a graph”, Congr. Numerantium, 139 (1999), 65–75 | MR | Zbl

[177] Staton W., “Some Ramsey-type numbers and the independence ratio”, Trans. Amer. Math. Soc., 256 (1979), 353–370 | DOI | MR | Zbl

[178] Szekeres G., Wilf H., “An inequality for the chromatic number of a graph”, J. Comb. Th., 4 (1968), 1–3 | DOI | MR

[179] Trinks M., “The Merrifield–Simmons conjecture holds for bipartite graphs”, J. Graph Th., 72:4 (2013), 478–486 | DOI | MR | Zbl

[180] Turán P., “On an extremal problem in graph theory”, Matematikai és Fizikai Lapok (in Hungarian), 48 (1941), 436–452

[181] Wagner S., Wang H., Yu G., “Molecular graphs and the inverse Wiener index problem”, Discr. Appl. Math., 157 (2009), 1544–1554 | DOI | MR | Zbl

[182] Wagner S. G., “Almost all trees have an even number of independent sets”, Electr. J. Comb., 16 (2009), #R93 | MR | Zbl

[183] Wagner S., Gutman I., “Maxima and minima of the Hosoya index and the Merrifield-Simmons index: a survey of results and techniques”, Acta Appl Math, 112 (2010), 323–346 | DOI | MR | Zbl

[184] Weber K., “On the number of stable sets in an $m\times n$ lattice”, Rostock Math. Kolloq., 34 (1988), 28–36 | MR | Zbl

[185] Wei V. K., A lower bound on the stability number of a simple graph, Bell Laboratories Technical Memorandum, No. 81-11217-9, 1981

[186] Weitz D., “Counting independent sets up to the tree threshold”, Proc. 38th Annual ACM Symp. Th. Comput., ACM, 2006, 140–149 | MR | Zbl

[187] Wilf H. S., “The number of maximal independent sets in a tree”, SIAM J. Algebraic Discr. Methods, 7 (1986), 125–130 | DOI | MR | Zbl

[188] Wood D. R., “On the maximum number of cliques in a graph”, Graphs and Combinatorics, 23:3 (2007), 337–352 | DOI | MR | Zbl

[189] Włoch I., “Trees with extremal numbers of maximal independent sets including the set of leaves”, Discr. Math., 308 (2008), 4768–4772 | DOI | MR

[190] Yeh L., “Fibonacci numbers of product graphs”, J. Comb. Math. Comb. Comput., 32 (2000), 223–229 | MR | Zbl

[191] Zhao Y., “The number of independent sets in a regular graph”, Combinatorics, Probability and Computing, 19 (2009), 315–320 | DOI | MR

[192] Zito J., “The structure and maximum number of maximum independent sets in trees”, J. Graph Th., 15:2 (1991), 207–221 | DOI | MR | Zbl