Planar domination graphs

被引：0
作者：
Eschen, EM
Klostermeyer, WF
Sritharan, R
机构：
[1] W Virginia Univ, Lane Dept Comp Sci & Elect Engn, Morgantown, WV 26506 USA
[2] Univ N Florida, Jacksonville, FL 32224 USA
[3] Univ Dayton, Dept Comp Sci, Dayton, OH 45469 USA
来源：
DISCRETE MATHEMATICS | 2003年 / 268卷 / 1-3期
关键词：
planar graph; weakly chordal graph; domination graph; recognition algorithm;
D O I：
10.1016/S0012-365X(02)00684-2
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A graph G is a domination graph if each induced subgraph of G has a pair of vertices such that the open neighborhood of one is contained in the closed neighborhood of the other in the subgraph. No polynomial time algorithm or hardness result is known for the problem of deciding whether a graph is a domination graph. In this paper, it is shown that the class of planar domination graphs is equivalent to the class of planar weakly chordal graphs, and thus, can be recognized in polynomial time. (C) 2002 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：129 / 137
页数：9
相关论文
共 50 条
  • [21] A NOTE ON SIGNED CYCLE DOMINATION IN GRAPHS
    Karami, Hossein
    Khoeilar, Rana
    Sheikholeslami, Seyed Mahmoud
    KRAGUJEVAC JOURNAL OF MATHEMATICS, 2013, 37 (01): : 159 - 162
  • [22] Largest planar graphs and largest maximal planar graphs of diameter two
    Yang, YS
    Lin, JH
    Dai, YJ
    JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2002, 144 (1-2) : 349 - 358
  • [23] Drawing Planar Graphs
    Rahman, Md Saidur
    Karim, Md Rezaul
    WALCOM: ALGORITHMS AND COMPUTATION (WALCOM 2020), 2020, 12049 : 3 - 14
  • [24] On the reconstruction of planar graphs
    Bilinski, Mark
    Kwon, Young Soo
    Yu, Xingxing
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2007, 97 (05) : 745 - 756
  • [25] Paired restraint domination in extended supergrid graphs
    Hung, Ruo-Wei
    Hung, Ling-Ju
    JOURNAL OF SUPERCOMPUTING, 2024, 80 (09) : 13217 - 13249
  • [26] Three conjectures on the signed cycle domination in graphs
    Guan, Jian
    Liu, Xiaoyan
    Lu, Changhong
    Miao, Zhengke
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2013, 25 (04) : 639 - 645
  • [27] Three conjectures on the signed cycle domination in graphs
    Jian Guan
    Xiaoyan Liu
    Changhong Lu
    Zhengke Miao
    Journal of Combinatorial Optimization, 2013, 25 : 639 - 645
  • [28] Planar median graphs and cubesquare-graphs
    Seemann, Carsten R.
    Moulton, Vincent
    Stadler, Peter F.
    Hellmuth, Marc
    DISCRETE APPLIED MATHEMATICS, 2023, 331 : 38 - 58
  • [29] Decomposing planar graphs into graphs with degree restrictions
    Cho, Eun-Kyung
    Choi, Ilkyoo
    Kim, Ringi
    Park, Boram
    Shan, Tingting
    Zhu, Xuding
    JOURNAL OF GRAPH THEORY, 2022, 101 (02) : 165 - 181
  • [30] LIGHT GRAPHS IN PLANAR GRAPHS OF LARGE GIRTH
    Hudak, Peter
    Macekova, Maria
    Madaras, Tomas
    Siroczki, Pavol
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2016, 36 (01) : 227 - 238
12345