Abstract
We consider the problem of constructing a graph having some given number of independent sets. The bounds are obtained for the number of vertices in bipartite graphs with the prescribed number of independent sets and the number of inclusion maximal independent sets.
Similar content being viewed by others
References
É. Czabarka, L. Székely, and S. Wagner, “The Inverse Problem for Certain Tree Parameters,” Discrete Appl. Math. 157(15), 3314–3319 (2009).
P. Erdös and T. Gallai, “Gráfok előírt fokú pontokkal,” Mat. Lapok. 11, 264–274 (1960).
V. Havel, “Poznámka o existenci konečných grafů,” Časopis pro pěstování matematiky 80(4), 477–480 (1955).
V. Linek, “Bipartite Graphs Can Have Any Number of Independent Sets,” Discrete Math. 76(2), 131–136 (1989).
S. Wagner, “A Class of Trees and Its Wiener Index,” Acta Appl. Math. 91(2), 119–132 (2006).
H. Wang and G. Yu, “All but 49 Numbers Are Wiener Indices of Trees,” Acta Appl. Math. 92(1), 15–20 (2006).
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © A.B. Dainyak, A.D. Kurnosov, 2015, published in Diskretnyi Analiz i Issledovanie Operatsii, 2015, Vol. 22, No. 1, pp. 19–30.
Rights and permissions
About this article
Cite this article
Dainyak, A.B., Kurnosov, A.D. On an extremal inverse problem in graph theory. J. Appl. Ind. Math. 9, 157–164 (2015). https://doi.org/10.1134/S1990478915020027
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1990478915020027