Geodesic
A criterion for a class of graphs to be a~boundary class and applications
Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 6, pp. 3-10.

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

A new definition of the boundary class of graphs is given and the corresponding criterion is proved. The class of all graphs in which every connected component is a tree with at most three leaves is considered as an example. This class is known to be the boundary class for several graph problems. We establish some sufficient conditions for this class to be a boundary class and prove that it is the boundary class for the bipartite subgraph and the planar subgraph problems. Bibl. 8.
Keywords: computational complexity, boundary class, maximum subgraph problem. 
@article{DA_2008_15_6_a0,
     author = {V. E. Alekseev and D. S. Malyshev},
     title = {A criterion for a class of graphs to be a~boundary class and applications},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {3--10},
     publisher = {mathdoc},
     volume = {15},
     number = {6},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2008_15_6_a0/}
}
TY  - JOUR
AU  - V. E. Alekseev
AU  - D. S. Malyshev
TI  - A criterion for a class of graphs to be a~boundary class and applications
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2008
SP  - 3
EP  - 10
VL  - 15
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2008_15_6_a0/
LA  - ru
ID  - DA_2008_15_6_a0
ER  - 
%0 Journal Article
%A V. E. Alekseev
%A D. S. Malyshev
%T A criterion for a class of graphs to be a~boundary class and applications
%J Diskretnyj analiz i issledovanie operacij
%D 2008
%P 3-10
%V 15
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2008_15_6_a0/
%G ru
%F DA_2008_15_6_a0
V. E. Alekseev; D. S. Malyshev. A criterion for a class of graphs to be a~boundary class and applications. Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 6, pp. 3-10. http://geodesic.mathdoc.fr/item/DA_2008_15_6_a0/

[1] Alekseev V. E., “O vliyanii lokalnykh ogranichenii na slozhnost opredeleniya chisla nezavisimosti grafa”, Kombinatorno-algebraicheskie metody v prikladnoi matematike, Izd-vo GGU, Gorkii, 1983, 3–13

[2] Alekseev V. E., Korobitsyn D. V., “O slozhnosti nekotorykh zadach na nasledstvennykh klassakh grafov”, Diskret. matematika, 4:4 (1992), 34–40 | MR | Zbl

[3] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[4] Alekseev V. E., “On easy and hard hereditary classes of graphs with respect to the independent set problem”, Discr. Appl. Math., 132 (2004), 17–26 | DOI | MR

[5] Alekseev V. E., Korobitsyn D. V., Lozin V. V., “Boundary classes of graphs for the dominating set problem”, Discr. Math., 285 (2004), 1–6 | DOI | MR | Zbl

[6] Alekseev V. E., Boliac R., Korobitsyn D. V., Lozin V. V., “NP-hard graph problems and boundary classes of graphs”, Theoret. Comp. Sci., 389 (2007), 219–236 | DOI | MR | Zbl

[7] Faria L., Figueiredo C. H., Mendonça C. F. X., “Splitting number is NP-complete”, Discr. Appl. Math., 108 (2001), 65–83 | DOI | MR | Zbl

[8] Faria L., Figueiredo C. H., Gravier S., Mendonça C. F. X, Stolfi J., “On maximum planar induced subgraphs”, Discr. Appl. Math., 154 (2006), 1774–1782 | DOI | MR | Zbl