Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2016, 10:1, 1-6
Volume 23, No 1, 2016, P. 5-16
UDC 519.17
V. E. Alekseev and D. V. Zakharova
Independent sets in graphs without subtrees with many leaves
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.
DOI: 10.17377/daio.2016.23.499
Vladimir E. Alekseev 1
Darya V. Zakharova 1
1. Nizhniy Novgorod State University,
23 Gagarin Ave., 603950 Nizhniy Novgorod, Russia
e-mail: aleve@rambler.ru, dvzakh@rambler.ru
Received 11 June 2015
Revised 25 June 2015
References
[1] V. E. Alekseev, A polynomial algorithm for finding the largest independent sets in claw-free graphs, Diskretn. Anal. Issled. Oper., Ser. 1, 6, No. 4, 3–19, 1999.[2] V. E. Alekseev and D. V. Zakharova, Independent sets in the graphs with bounded minors of the extended incidence matrix, Diskretn. Anal. Issled. Oper., 17, No. 1, 3–10, 2010. Translated in J. Appl. Ind. Math., 5, No. 1, 14–18, 2011.
[3] V. E. Alekseev and D. V. Korobitsyn, Complexity of some problems on hereditary classes of graphs, Diskretn. Mat., 4, No. 4, 34–40, 1992.
[4] V. E. Alekseev and D. S. Malyshev, Planar graph classes with the independent set problem solvable in polynomial time, Diskretn. Anal. Issled. Oper., 15, No. 1, 3–10, 2008. Translated in J. Appl. Ind. Math., 3, No. 1, 1–4, 2009.
[5] V. E. Alekseev and V. A. Talanov, Grafy i algoritmy. Struktury dannykh. Modeli vychislenii (Graphs and Algorithms. Data Structures. Computation Models), Internet-Univ. Inform. Tekhnol., BINOM. Lab. Znanii, Moscow, 2006.
[6] A. V. Bankevich and D. V. Karpov, Bounds of the number of leaves of spanning trees, Zap. Nauchn. Semin. POMI, 391, 18–34, 2011. Translated in J. Math. Sci., New York, 184, No. 5, 564–572, 2012.
[7] D. V. Zakharova, Weighted independent sets in graphs with bounded minors of the extended incidence matrix, in Materialy X Mezhdunarodnogo seminara “Diskretnaya matematika i ee prilozheniya” (Proc. X Int. Seminar “Discrete Math. and Its Applications”), Moscow, Russia, Jan. 1–6, 2010, pp. 303–305, Izd. Mekh.-Mat. Fak. MGU, Moscow, 2010.
[8] D. S. Malyshev, Classes of subcubic planar graphs for which the independent set problem is polynomially solvable, Diskretn. Anal. Issled. Oper., 20, No. 3, 26–44, 2013. Translated in J. Appl. Ind. Math., 7, No. 4, 537–548, 2013.
[9] V. N. Shevchenko, Kachestvennye voprosy tselochislennogo programmirovaniya (Qualitative Problems in Integer Programming), Nauka, Moscow, 1995.
[10] P. Erdõs and G. Szekeres, A combinatorial problem in geometry, Compos. Math., 2, 463–470, 1935.
[11] G. J. Minty, On maximal independent sets of vertices in claw-free graphs, J. Comb. Theory, Ser. B, 28, 284–304, 1980.
[12] N. Sbihi, Algorithme de recherche d’un stable de cardinalit´e maximum dans un graphe sans ´etoile, Discrete Math., 29, No. 1, 53–76, 1980.
