Volume 16, No 2, 2009, P. 85-94

UDC 519.178
D. S. Malyshev
Boundary classes of graphs for some recognition problems

Abstract:
The class of all graphs in which every connected component is a tree with at most three leaves and the class of line graphs of this class are considered in the article. There is a series of well-known problems for which these classes are boundary classes.We study common properties of such problems. Namely, we prove a sufficient condition for the considered classes to be boundary classes. Using the obtained tool we add 8 new cases of given classes being boundary classes to known ones.
Bibl. 10.

Keywords: extremal graph problems, computational complexity, boundary class.

Malyshev Dmitry Sergeevich ¹
1. Nizhegorodskiy State University,
23 Gagarin ave., building 2, 603950 N. Novgorod, Russia
e-mail: ave@uic.nnov.ru