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 条
  • [1] Generalized independence and domination in graphs
    Borowiecki, M
    Michalak, D
    DISCRETE MATHEMATICS, 1998, 191 (1-3) : 51 - 56
  • [2] Independence and k-domination in graphs
    Hansberg, Adriana
    Meierling, Dirk
    Volkmann, Lutz
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2011, 88 (05) : 905 - 915
  • [3] CHARACTERIZATION OF GRAPHS WITH EQUAL DOMINATION NUMBERS AND INDEPENDENCE NUMBERS
    Jou, Min-Jen
    TAIWANESE JOURNAL OF MATHEMATICS, 2010, 14 (04): : 1537 - 1542
  • [4] Independence number in path graphs
    Knor, M
    Niepel, L
    COMPUTING AND INFORMATICS, 2004, 23 (02) : 179 - 187
  • [5] Independence and Inverse Domination in Complete z-Ary Tree and Jahangir Graphs
    Omran, Ahmed A.
    EL-Seidy, Essam
    BOLETIM SOCIEDADE PARANAENSE DE MATEMATICA, 2023, 41 : 13 - 13
  • [6] THE DOMINATION COVER PEBBLING NUMBER FOR SOME CYCLIC GRAPHS AND PATH GRAPHS
    Lourdusamy, A.
    Mathivanan, T.
    ARS COMBINATORIA, 2018, 138 : 51 - 61
  • [7] Smallest domination number and largest independence number of graphs and forests with given degree sequence
    Gentner, Michael
    Henning, Michael A.
    Rautenbach, Dieter
    JOURNAL OF GRAPH THEORY, 2018, 88 (01) : 131 - 145
  • [8] Connected Domination Number and a New Invariant in Graphs with Independence Number Three
    Bercov, Vladimir
    COMPUTER SCIENCE JOURNAL OF MOLDOVA, 2021, 29 (01) : 96 - 104
  • [9] Progressive Algorithms for Domination and Independence
    Fabianski, Grzegorz
    Pilipczuk, Michal
    Siebertz, Sebastian
    Torunczyk, Szymon
    36TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2019), 2019,
  • [10] Independent domination in directed graphs
    Cary, Michael
    Cary, Jonathan
    Prabhu, Savari
    COMMUNICATIONS IN COMBINATORICS AND OPTIMIZATION, 2021, 6 (01) : 67 - 80
12345