Volume 17, No 1, 2010, P. 3-10

UDC 519.17
V. E. Alekseev, D. V. Zakharova
Independence sets of graphs with bounded minors of the augmented incidence matrix

Abstract:
We characterize the graphs with bounded minors of augmented incidence matrix. We also prove that the independence set problem can be solved in polynomial time for graphs with bounded minors of incidence matrix with an added column of units.
Bibl. 6.

Keywords: augmented incidence matrix, minor, independence set problem.

Alekseev Vladimir Evgenyevich ¹
Zakharova Darya Vladimirovna ¹
1. Nizhny Novgorod State University,
23 Gagarin ave., 603950 Nizhny Novgorod
e-mail: ave@uic.nnov.ru