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 条
  • [21] On restricted domination in graphs
    Samodivkin, Vladimir
    MATHEMATICA SLOVACA, 2007, 57 (05) : 401 - 406
  • [22] DOMINATION VALUE IN GRAPHS
    Yi, Eunjeong
    CONTRIBUTIONS TO DISCRETE MATHEMATICS, 2012, 7 (02) : 30 - 43
  • [23] On domination in signed graphs
    Joseph, James
    Joseph, Mayamma
    ACTA UNIVERSITATIS SAPIENTIAE INFORMATICA, 2023, 15 (01) : 1 - 9
  • [24] The Arrow Domination in Graphs
    Radhi, Suha J.
    Abdlhusein, Mohammed A.
    Hashoosh, Ayed E.
    INTERNATIONAL JOURNAL OF NONLINEAR ANALYSIS AND APPLICATIONS, 2021, 12 (01): : 473 - 480
  • [25] Tadpole Domination in Graphs
    Al-Harere, M. N.
    Bakhash, P. A. Khuda
    BAGHDAD SCIENCE JOURNAL, 2018, 15 (04) : 466 - 471
  • [26] Clique domination in graphs
    Xu, Guangjun
    Shan, Erfang
    Zhao, Min
    ARS COMBINATORIA, 2010, 97A : 169 - 180
  • [27] Bottleneck domination and bottleneck independent domination on graphs
    Yen, WCK
    JOURNAL OF INFORMATION SCIENCE AND ENGINEERING, 2002, 18 (02) : 311 - 331
  • [28] GRAPHS WITH EQUAL DOMINATION AND INDEPENDENT DOMINATION NUMBER
    Vaidya, S. K.
    Pandit, R. M.
    TWMS JOURNAL OF APPLIED AND ENGINEERING MATHEMATICS, 2015, 5 (01): : 74 - 79
  • [29] Pitchfork domination in graphs
    Al-Harere, Manal N.
    Abdlhusein, Mohammed A.
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2020, 12 (02)
  • [30] Captive domination in graphs
    Al-Harere, Manal N.
    Omran, Ahmed A.
    Breesam, Athraa T.
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2020, 12 (06)
12345