Geodesic
Structural and algorithmic properties of maximal dissociating sets in graphs
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 28 (2022) no. 2, pp. 114-142

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

A subset of the vertex set of a graph is called dissociating if the degrees of the vertices of the subgraph generated by this subset do not exceed $1$. A dissociating set is maximal if it is not contained in any dissociating set with a greater number of vertices. Estimates for the greatest (smallest) number of vertices in a maximal dissociating set of a graph are proposed. It is proved that the problem of finding a maximal dissociating set of smallest cardinality is NP-hard for quasichordal bipartite graphs. In addition, it is proved that the problem of finding a maximal dissociating set of smallest cardinality is NP-hard for chordal bipartite graphs, bipartite graphs with the greatest degree of a vertex equal to 3, planar graphs with large girth, and for classes of graphs characterized by finite lists of forbidden generated biconnected subgraphs. A linear algorithm for solving the latter problem in the class of trees is proposed.
Keywords: maximal dissociating set of a graph, problem of finding a maximal generated subgraph with maximum degree of a vertex at most 1, perfect elimination bipartite graph, NP-completeness, hereditary graph classes, trees.
Mots-clés : maximal dissociation set 
@article{TIMM_2022_28_2_a9,
     author = {O. I. Duginov and B. M. Kuskova and D. S. Malyshev and N. A. Shur},
     title = {Structural and algorithmic properties of maximal dissociating sets in graphs},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {114--142},
     publisher = {mathdoc},
     volume = {28},
     number = {2},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2022_28_2_a9/}
}
TY  - JOUR
AU  - O. I. Duginov
AU  - B. M. Kuskova
AU  - D. S. Malyshev
AU  - N. A. Shur
TI  - Structural and algorithmic properties of maximal dissociating sets in graphs
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2022
SP  - 114
EP  - 142
VL  - 28
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMM_2022_28_2_a9/
LA  - ru
ID  - TIMM_2022_28_2_a9
ER  - 
%0 Journal Article
%A O. I. Duginov
%A B. M. Kuskova
%A D. S. Malyshev
%A N. A. Shur
%T Structural and algorithmic properties of maximal dissociating sets in graphs
%J Trudy Instituta matematiki i mehaniki
%D 2022
%P 114-142
%V 28
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMM_2022_28_2_a9/
%G ru
%F TIMM_2022_28_2_a9
O. I. Duginov; B. M. Kuskova; D. S. Malyshev; N. A. Shur. Structural and algorithmic properties of maximal dissociating sets in graphs. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 28 (2022) no. 2, pp. 114-142. http://geodesic.mathdoc.fr/item/TIMM_2022_28_2_a9/