Diskretnyi Analiz i Issledovanie Operatsii
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






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


Diskretn. Anal. Issled. Oper., 2016, Volume 23, Issue 1, Pages 5–16 (Mi da835)  

Independent sets in graphs without subtrees with many leaves

V. E. Alekseev, D. V. Zakharova

Nizhniy Novgorod State University, 23 Gagarin Ave., 603950 Nizhniy Novgorod, Russia

Abstract: A subtree of a graph is called inscribed if there is no three vertices in the subtree inducing a triangle in the graph. We prove that for any fixed k the independent set problem is solvable in polynomial time for each of the following classes of graphs: 1) the graphs without subtrees with $k$ leaves, 2) the subcubic graphs without inscribed subtrees with $k$ leaves, 3) the graphs with degrees not exceeding $k$ without induced subtrees with 4 leaves. Ill. 1, bibliogr. 12.

Keywords: graph, independent set, forbidden subtree, polynomial algorithm.

Funding Agency Grant Number
Russian Foundation for Basic Research 14-01-00515


DOI: https://doi.org/10.17377/daio.2016.23.499

Full text: PDF file (271 kB)
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2016, 10:1, 1–6

Bibliographic databases:

UDC: 519.17
Received: 11.06.2015
Revised: 25.06.2015

Citation: V. E. Alekseev, D. V. Zakharova, “Independent sets in graphs without subtrees with many leaves”, Diskretn. Anal. Issled. Oper., 23:1 (2016), 5–16; J. Appl. Industr. Math., 10:1 (2016), 1–6

Citation in format AMSBIB
\Bibitem{AleZak16}
\by V.~E.~Alekseev, D.~V.~Zakharova
\paper Independent sets in graphs without subtrees with many leaves
\jour Diskretn. Anal. Issled. Oper.
\yr 2016
\vol 23
\issue 1
\pages 5--16
\mathnet{http://mi.mathnet.ru/da835}
\crossref{https://doi.org/10.17377/daio.2016.23.499}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3555672}
\elib{https://elibrary.ru/item.asp?id=25792209}
\transl
\jour J. Appl. Industr. Math.
\yr 2016
\vol 10
\issue 1
\pages 1--6
\crossref{https://doi.org/10.1134/S1990478916010014}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84961602268}


Linking options:
  • http://mi.mathnet.ru/eng/da835
  • http://mi.mathnet.ru/eng/da/v23/i1/p5

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Дискретный анализ и исследование операций
    Number of views:
    This page:195
    Full text:62
    References:54
    First page:34

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021