×

On the maximum number of maximum independent sets of bipartite graphs. (English) Zbl 1541.05134

Summary: An independent set in a graph \(G\) is a set of pairwise nonadjacent vertices of \(G\). The independence number, \(\alpha\), of \(G\) is the maximum cardinality of an independent set in \(G\). An independent set in \(G\) is maximum if it has cardinality \(\alpha\). E. Mohr and D. Rautenbach [Graphs Comb. 34, No. 6, 1729–1740 (2018; Zbl 1402.05169)] determined the \(n\)-vertex trees (resp. connected graphs, disconnected graphs) with independence number \(\alpha\) having the largest number of maximum independent sets. As a continuance of these works, we give complete characterizations among the following families of graphs:
the \(n\)-vertex forests with independence number \(\alpha\) having the first three largest number of maximum independent sets;
the \(n\)-vertex trees with independence number \(\alpha\) having the second and third largest number of maximum independent sets;
the bipartite graphs (containing at least one cycle) of order \(n\) and independence number \(\alpha\) having the maximum number of maximum independent sets;
the disconnected \(n\)-vertex graphs with independence number \(\alpha\) having the second largest number of maximum independent sets.
Furthermore, we obtain a complete classification of connected graphs with order \(n\) and independence number \(n - 3\), which gives a solution to an open problem of Derikvand and Oboudi.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C35 Extremal problems in graph theory

Citations:

Zbl 1402.05169
Full Text: DOI

References:

[1] Arumugam, S.; Haynes, TW; Henning, MA; Nigussie, Y., Maximal independent sets in minimum colorings, Discrete Math., 311, 13, 1158-1163, 2011 · Zbl 1222.05045 · doi:10.1016/j.disc.2010.06.045
[2] Bruyère, V.; Joret, G.; Mélot, H., Trees with given stability number and minimum number of stable sets, Graphs Combin., 28, 2, 167-187, 2012 · Zbl 1256.05161 · doi:10.1007/s00373-011-1041-2
[3] Bruyère, V.; Mélot, H., Fibonacci index and stability number of graphs: a polyhedral study, J. Comb. Optim., 18, 3, 207-228, 2009 · Zbl 1203.05074 · doi:10.1007/s10878-009-9228-7
[4] Derikvand, T.; Oboudi, MR, On the number of maximum independent sets of graphs, Trans. Comb., 3, 29-36, 2014 · Zbl 1463.05399
[5] Hua, HB; Hou, YP, On graphs with the third largest number of maximal independent sets, Inform. Process. Lett., 109, 4, 248-253, 2009 · Zbl 1189.05133 · doi:10.1016/j.ipl.2008.10.013
[6] Jin, ZM; Li, XL, Graphs with the second largest number of maximal independent sets, Discrete Math., 308, 5864-5870, 2008 · Zbl 1219.05122 · doi:10.1016/j.disc.2007.10.032
[7] Jin, ZM; Yan, SHF, Trees with the second and third largest number of maximal independent sets, Ars Combin., 93, 341-351, 2009 · Zbl 1224.05096
[8] Jou, MJ; Chang, GJ, The number of maximum independent sets in graphs, Taiwan. J. Math., 4, 685-695, 2000 · Zbl 0967.05038 · doi:10.11650/twjm/1500407302
[9] Jou, MJ; Lin, JJ, Trees with the second largest number of maximal independent sets, Discrete Math., 309, 4469-4474, 2009 · Zbl 1187.05026 · doi:10.1016/j.disc.2009.02.007
[10] Lehner, F.; Wagner, S., Maximizing the number of independent sets of fixed size in connected graphs with given independence number, Graphs Combin., 33, 1103-1118, 2017 · Zbl 1395.05129 · doi:10.1007/s00373-017-1825-0
[11] Li, SC; Jing, W., Maximal independent sets in graphs with cyclomatic number at most two, Util. Math., 83, 107-120, 2010 · Zbl 1242.05207
[12] Li, SC; Zhang, HH; Zhang, XY, Maximal independent sets in bipartite graphs with at least one cycle, Discrete Math. Theor. Comput. Sci., 15, 243-258, 2013 · Zbl 1283.05206
[13] Liu, JQ, Maximal independent sets of bipartite graphs, J. Graph Theory, 17, 4, 495-507, 1993 · Zbl 0783.05063 · doi:10.1002/jgt.3190170407
[14] Merrifield, RE; Simmons, HE, Topological Methods in Chemistry, 1989, New York: Wiley, New York
[15] Mohr, E.; Rautenbach, D., On the maximum number of maximum independent sets, Graphs Combin., 34, 1729-1740, 2018 · Zbl 1402.05169 · doi:10.1007/s00373-018-1969-6
[16] Mohr, E.; Rautenbach, D., On the maximum number of maximum independent sets in connected graphs, J. Graph Theory, 96, 4, 510-521, 2021 · Zbl 1521.05072 · doi:10.1002/jgt.22629
[17] Moon, JW; Moser, L., On cliques in graphs, Isr. J. Math., 3, 23-28, 1965 · Zbl 0144.23205 · doi:10.1007/BF02760024
[18] Ortiz, C.; Villanueva, M., Maximal independent sets in caterpillar graphs, Discrete Appl. Math., 160, 3, 259-266, 2012 · Zbl 1236.05154 · doi:10.1016/j.dam.2011.10.024
[19] Prodinger, H.; Tichy, RF, Fibonacci numbers of graphs, Fibonacci Quart., 20, 1, 16-21, 1982 · Zbl 0475.05046
[20] Sagan, BE; Vatter, VR, Maximal and maximum independent sets in graphs with at most \(r\) cycles, J. Graph Theory, 53, 283-314, 2006 · Zbl 1107.05047 · doi:10.1002/jgt.20186
[21] Turán, P., Eine Extremalaufgabe aus der Graphentheorie, Mat. és Fiz. Lapok, 48, 436-452, 1941 · JFM 67.0732.03
[22] 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, 3, 323-346, 2010 · Zbl 1201.92068 · doi:10.1007/s10440-010-9575-5
[23] West, D.B.: Introduction to Graph Theory, 2nd edn. Pearson Eduction Inc (2001)
[24] Ying, GC; Meng, KK; Sagan, BE; Vatter, VR, Maximal independent sets in graphs with at most \(r\) cycles, J. Graph Theory, 53, 4, 270-282, 2006 · Zbl 1107.05044 · doi:10.1002/jgt.20185
[25] Zito, J., The structure and maximum number of maximum independent sets in trees, J. Graph Theory, 15, 207-221, 1991 · Zbl 0764.05082 · doi:10.1002/jgt.3190150208
[26] Zykov, AA, On some properties of linear complexes, Mat. Sb. Novaya Seriya, 24, 163-188, 1949 · Zbl 0033.02602
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.