EN|RU Volume 19, No 4, 2012, P. 66-72 UDC 519.178 D. S. Malyshev  Polynomial solvability of the independent set problem for one class of graphs with small diameter Abstract: A constructive approach to forming new cases in the family of hereditary parts of the set ${\mathcal Free}(\{P_5,C_5\})$ with polynomial-time solvability of the independent set problem is considered. We prove that if this problem is polynomial-time solvable in the class ${\mathcal Free}(\{P_5,C_5,G\})$ then for any graph $H$ which can inductively be obtained from $G$ by means of applying addition with $K_1$ or multiplication by $K_1$ to the graph $G$ the problem has the same computational status in ${\mathcal Free}(\{P_5,C_5,H\})$. Bibliogr. 10. Keywords: the independent set problem, computational complexity, polynomial algorithm. Malyshev Dmitrii Sergeevich 1,2 1. Nizhniy Novgorod Higher School of Economics, 25/12 B. Pecherskaya str., 603155 Nizhny Novgorod, Russia 2. Nizhniy Novgorod State University, 23 Gagarina ave., 603950 Nizhniy Novgorod, Russia e-mail: dsmalyshev@rambler.ru © Sobolev Institute of Mathematics, 2015