INDEPENDENCE AND DOMINATION IN PATH GRAPHS OF TREES

被引：0
作者：
Niepel, Ludovit [1 ]
Cerny, Anton [1 ]
机构：
[1] Kuwait Univ, Dept Math & Comp Sci, Kuwait 13060, Kuwait
来源：
COMPUTING AND INFORMATICS | 2008年 / 27卷 / 04期
关键词：
Path graph; dominating set; independent set;
D O I：
暂无
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
The problems of determining the maximum cardinality of an independent set of vertices and the minimum cardinality of a, maximal independent set of vertices of a. graph are known to be NP-complete. We provide efficient algorithms for finding these values for path graphs of trees.
引用
收藏
页码：581 / 591
页数：11
相关论文
共 50 条
  • [41] Connected domination in random graphs
    Gábor Bacsó
    József Túri
    Zsolt Tuza
    Indian Journal of Pure and Applied Mathematics, 2023, 54 : 439 - 446
  • [42] Roman edge domination in graphs
    Soner, N. D.
    Chaluvaraju, B.
    Srivastava, J. P.
    PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES INDIA SECTION A-PHYSICAL SCIENCES, 2009, 79A : 45 - 50
  • [43] CHARACTERISATION OF GRAPHS ON DOMINATION PARAMETERS
    Avadayappan, Selvam
    Senthilkumar, C. S.
    ARS COMBINATORIA, 2012, 103 : 423 - 431
  • [44] Domination in Fuzzy Directed Graphs
    Enriquez, Enrico
    Estrada, Grace
    Loquias, Carmelita
    Bacalso, Reuella J.
    Ocampo, Lanndon
    MATHEMATICS, 2021, 9 (17)
  • [45] Restrained domination in signed graphs
    Mathias, Anisha Jean
    Sangeetha, V
    Acharya, Mukti
    ACTA UNIVERSITATIS SAPIENTIAE-MATHEMATICA, 2020, 12 (01) : 155 - 163
  • [46] Connected monophonic domination in graphs
    Sadiquali, A.
    Arul Paul Sudhahar, P.
    Lakshmana Gomathi Nayagam, V.
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2021, 13 (03)
  • [47] Isolate Roman domination in graphs
    Bakhshesh, Davood
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2022, 14 (03)
  • [48] Resolving Restrained Domination in Graphs
    Monsanto, Gerald B.
    Rara, Helen M.
    EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS, 2021, 14 (03): : 829 - 841
  • [49] On the roots of domination polynomial of graphs
    Oboudi, Mohammad Reza
    DISCRETE APPLIED MATHEMATICS, 2016, 205 : 126 - 131
  • [50] Regular set domination in graphs
    Kulli, V. R.
    Janakiram, B.
    NATIONAL ACADEMY SCIENCE LETTERS-INDIA, 2009, 32 (11-12): : 351 - 355
12345