Independent sets in graphs without subtrees with many leaves

被引：0
作者：
Alekseev V.E. [1 ]
Zakharova D.V. [1 ]
机构：
[1] Lobachevsky State University of Nizhny Novgorod, pr. Gagarina 23, korp. 2, Nizhny Novgorod
来源：
Journal of Applied and Industrial Mathematics | 2016年 / 10卷 / 1期
关键词：
forbidden subtree; graph; independent set; polynomial algorithm;
D O I：
10.1134/S1990478916010014
中图分类号：
学科分类号：
摘要：
A subtree of a graph is called inscribed if no three vertices of the subtree generate a triangle in the graph. We prove that, for fixed k, the independent set problem is solvable in polynomial time for each of the following classes of graphs: (1) graphs without subtrees with k leaves, (2) subcubic graphs without inscribed subtrees with k leaves, and (3) graphs with degree not exceeding k and lacking induced subtrees with four leaves. © 2016, Pleiades Publishing, Ltd.
引用
收藏
页码：1 / 6
页数：5
相关论文
共 12 条
  • [1] Alekseev V.E., A Polynomial Algorithm for Finding the Largest Independent Sets in Claw-Free Graphs, Diskret. Anal. Issled. Oper. Ser. 1, 6, 4, pp. 3-19, (1999)
  • [2] Alekseev V.E., Korobitsyn D.V., Complexity of Some Problems on Hereditary Classes of Graphs, Diskret. Mat., 4, 4, pp. 34-40, (1992)
  • [3] Alekseev V.E., Malyshev D.S., Planar Graph Classes with the Independent Set Problem Solvable in Polynomial Time, Diskret. Anal. Issled. Oper., 15, 1, pp. 3-10, (2008)
  • [4] Alekseev V.E., Talanov V.A., Graphs and Algorithms. Data Structures. Computation Models, (2006)
  • [5] Alekseev V.E., Zakharova D.V., Independent Sets in the Graphs with Bounded Minors of the Extended Incidence Matrix, Diskret. Anal. Issled. Oper., 17, 1, pp. 3-10, (2010)
  • [6] Bankevich A.V., Karpov D.V., Bounds of the Number of Leaves of Spanning Trees, Zap. Nauchn. Sem. St.-Petersburg. Otdel. Mat. Inst. Steklov. (POMI), 391, pp. 18-34, (2011)
  • [7] Erdos P., Szekeres G., A Combinatorial Problem in Geometry, CompositioMath., 2, pp. 463-470, (1935)
  • [8] Malyshev D.S., Classes ofSubcubicPlanarGraphs forWhich the Independent Set Problem Is Polynomially Solvable, Diskret. Anal. Issled. Oper., 20, 3, pp. 26-44, (2013)
  • [9] Minty G.J., On Maximal Independent Sets of Vertices in Claw-Free Graphs, J. Combin. Theory Ser. B, 28, pp. 284-304, (1980)
  • [10] Sbihi N., Algorithme de recherche d’un stable de cardinalitémaximum dans un graphe sans étoile, Discrete Math., 29, 1, pp. 53-76, (1980)
12