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 条
  • [31] Independent transversal domination subdivision number of trees
    Pushpam, P. Roushini Leely
    Bhanthavi, K. Priya
    COMMUNICATIONS IN COMBINATORICS AND OPTIMIZATION, 2024,
  • [32] HEREDITARY EQUALITY OF DOMINATION AND EXPONENTIAL DOMINATION IN SUBCUBIC GRAPHS
    Chen, Xue-Gang
    Wang, Yu-Feng
    Wu, Xiao-Fei
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2021, 41 (04) : 1067 - 1075
  • [33] Perfect Roman domination in trees
    Henning, Michael A.
    Klostermeyer, William F.
    MacGillivray, Gary
    DISCRETE APPLIED MATHEMATICS, 2018, 236 : 235 - 245
  • [34] On computing secure domination of trees
    Poureidi, Abolfazl
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2021, 13 (05)
  • [35] Secure connected domination and secure total domination in unit disk graphs and rectangle graphs ✩
    Wang, Cai-Xia
    Yang, Yu
    Xu, Shou-Jun
    THEORETICAL COMPUTER SCIENCE, 2023, 957
  • [36] Trees with large m-eternal domination number
    Henning, Michael A.
    Klostermeyer, William F.
    DISCRETE APPLIED MATHEMATICS, 2016, 211 : 79 - 85
  • [37] Broadcast Domination in Subcubic Graphs
    Yang, Wei
    Wu, Baoyindureng
    GRAPHS AND COMBINATORICS, 2022, 38 (06)
  • [38] Resolving domination number of graphs
    Alfarisi, Ridho
    Dafik
    Kristiana, Arika Indah
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2019, 11 (06)
  • [39] Transferable domination number of graphs
    Chang, Fei-Huang
    Chia, Ma-Lian
    Kuo, David
    Deng, Wen
    Liaw, Sheng-Chyang
    Pan, Zhishi
    DISCRETE APPLIED MATHEMATICS, 2022, 313 : 135 - 146
  • [40] Neighborhood and Domination Polynomials of Graphs
    Irene Heinrich
    Peter Tittmann
    Graphs and Combinatorics, 2018, 34 : 1203 - 1216
12345