Volume 22, No 1, 2015, P. 19-31
UDC 519.176
A. B. Dainiak, A. D. Kurnosov
On an extremal inverse problem in graph theory
Abstract:
Upper bounds are obtained for minimal number of vertices in graphs having prescribed number of maximal independent sets.
Ill. 1, bibliogr. 6.
Keywords: inverse problem, independent set, bipartite graph.
DOI: 10.17377/daio.2015.22.445
Alexander B. Dainiak 1
ArtemD.Kurnosov 1
1. Moscow Institute of Physics and Technology,
9 Institutskii per., 141700 Dolgoprudnyi, Russia
å-mail: dainiak@phystech.edu, kurnosov@phystech.edu
Received 11 March 2014
Revised 12 September 2014
References
[1] É. Czabarka, L. Székely, and S. Wagner, The inverse problem for certain tree parameters, Discrete Appl. Math., 157, No. 15, 3314–3319, 2009.
[2] P. Erdös and T. Gallai, Graphs with prescribed degrees of vertices, Mat. Lapok., 11, 264–274, 1960.
[3] V. Havel, A remark on the existence of finite graphs, Čas. Pěstování Mat., 80, No. 4, 477–480, 1955.
[4] V. Linek, Bipartite graphs can have any number of independent sets, Discrete Math., 76, No. 2, 131–136, 1989.
[5] S. Wagner, A class of trees and its Wiener index, Acta Appl. Math., 91, No. 2, 119–132, 2006.
[6] H. Wang and G. Yu, All but 49 numbers are Wiener indices of trees, Acta Appl. Math., 92, No. 1, 15–20, 2006.
