Geodesic
Boundary classes of graphs for some recognition problems
Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 2, pp. 85-94

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2009_16_2_a6,
     author = {D. S. Malyshev},
     title = {Boundary classes of graphs for some recognition problems},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {85--94},
     publisher = {mathdoc},
     volume = {16},
     number = {2},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2009_16_2_a6/}
}
TY  - JOUR
AU  - D. S. Malyshev
TI  - Boundary classes of graphs for some recognition problems
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2009
SP  - 85
EP  - 94
VL  - 16
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2009_16_2_a6/
LA  - ru
ID  - DA_2009_16_2_a6
ER  - 
%0 Journal Article
%A D. S. Malyshev
%T Boundary classes of graphs for some recognition problems
%J Diskretnyj analiz i issledovanie operacij
%D 2009
%P 85-94
%V 16
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2009_16_2_a6/
%G ru
%F DA_2009_16_2_a6
D. S. Malyshev. Boundary classes of graphs for some recognition problems. Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 2, pp. 85-94. http://geodesic.mathdoc.fr/item/DA_2009_16_2_a6/