EN|RU

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.edukurnosov@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.

 © Sobolev Institute of Mathematics, 2015