Geodesic
A constructive existence theorem related to local transformations of graphs for the independent set problem
Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 21 (2019) no. 2, pp. 215-221

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

For a given graph, the independent set problem is to find the size of a maximum set of pairwise non-adjacent its vertices. There are numerous cases of NP-hardness and polynomial-time solvability of this problem. To determine a computational status of the independent set problem, local transformations of graphs are often used. The paper considers some class of replacements of subgraphs in graphs that change the independence number in a controllable way. Every such local transform of a graph is determined by some pattern which is a subset of the power set. It is obvious that this pattern must be gradable. The paper shows that replacing subgraph exists for any gradable pattern.
Keywords: independent set problem, graph with given properties.
Mots-clés : local transformation 
@article{SVMO_2019_21_2_a4,
     author = {D. V. Sirotkin and D. S. Malyshev},
     title = {A constructive existence theorem related to local transformations of graphs for the independent set problem},
     journal = {\v{Z}urnal Srednevol\v{z}skogo matemati\v{c}eskogo ob\^{s}estva},
     pages = {215--221},
     publisher = {mathdoc},
     volume = {21},
     number = {2},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SVMO_2019_21_2_a4/}
}
TY  - JOUR
AU  - D. V. Sirotkin
AU  - D. S. Malyshev
TI  - A constructive existence theorem related to local transformations of graphs for the independent set problem
JO  - Žurnal Srednevolžskogo matematičeskogo obŝestva
PY  - 2019
SP  - 215
EP  - 221
VL  - 21
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SVMO_2019_21_2_a4/
LA  - ru
ID  - SVMO_2019_21_2_a4
ER  - 
%0 Journal Article
%A D. V. Sirotkin
%A D. S. Malyshev
%T A constructive existence theorem related to local transformations of graphs for the independent set problem
%J Žurnal Srednevolžskogo matematičeskogo obŝestva
%D 2019
%P 215-221
%V 21
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SVMO_2019_21_2_a4/
%G ru
%F SVMO_2019_21_2_a4
D. V. Sirotkin; D. S. Malyshev. A constructive existence theorem related to local transformations of graphs for the independent set problem. Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 21 (2019) no. 2, pp. 215-221. http://geodesic.mathdoc.fr/item/SVMO_2019_21_2_a4/