Trudy Instituta Matematiki i Mekhaniki UrO RAN
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


Trudy Inst. Mat. i Mekh. UrO RAN:
Year:
Volume:
Issue:
Page:
Find




Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register

Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2022, Volume 28, Number 2, Pages 114–142
DOI: https://doi.org/10.21538/0134-4889-2022-28-2-114-142 (Mi timm1909) 		 
Structural and algorithmic properties of maximal dissociating sets in graphs

O. I. Duginova, B. M. Kuskovaa, D. S. Malyshevb, N. A. Shura

a Belarusian State University, Minsk
b National Research University – Higher School of Economics in Nizhny Novgorod
Full-text PDF (398 kB)
References:
PDF
HTML
DOI: https://doi.org/10.21538/0134-4889-2022-28-2-114-142
Abstract: 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, maximal dissociation set, perfect elimination bipartite graph, NP-completeness, hereditary graph classes, trees.
Funding agency Grant number
Russian Foundation for Basic Research 20-51-04001
Belarusian Republican Foundation for Fundamental Research Ф21РМ-001
The research of the third author was supported by the Russian Foundation for Basic Research (project no. 20-51-04001). The research of the first and the fourth authors was supported by the Belarusian Republican Foundation for Fundamental Research (project no. F21RM-001).
Received: 22.02.2022
Revised: 04.05.2022
Accepted: 11.05.2022
Bibliographic databases:
Document Type: Article
UDC: 519.1
MSC: 05C70
Language: Russian
Citation: O. I. Duginov, B. M. Kuskova, D. S. Malyshev, N. A. Shur, “Structural and algorithmic properties of maximal dissociating sets in graphs”, Trudy Inst. Mat. i Mekh. UrO RAN, 28, no. 2, 2022, 114–142
Citation in format AMSBIB
\Bibitem{DugKusMal22}
\by O.~I.~Duginov, B.~M.~Kuskova, D.~S.~Malyshev, N.~A.~Shur
\paper Structural and algorithmic properties of maximal dissociating sets in graphs
\serial Trudy Inst. Mat. i Mekh. UrO RAN
\yr 2022
\vol 28
\issue 2
\pages 114--142
\mathnet{http://mi.mathnet.ru/timm1909}
\crossref{https://doi.org/10.21538/0134-4889-2022-28-2-114-142}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4453862}
\elib{https://elibrary.ru/item.asp?id=48585953}
Linking options:
  • https://www.mathnet.ru/eng/timm1909
  • https://www.mathnet.ru/eng/timm/v28/i2/p114
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Trudy Instituta Matematiki i Mekhaniki UrO RAN
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024