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 条
  • [31] The monadic second-order logic of graphs XII: planar graphs and planar maps
    Courcelle, B
    [J]. THEORETICAL COMPUTER SCIENCE, 2000, 237 (1-2) : 1 - 32
  • [32] ON THE QUEUE NUMBER OF PLANAR GRAPHS
    Di Battista, Giuseppe
    Frati, Fabrizio
    Pach, Janos
    [J]. SIAM JOURNAL ON COMPUTING, 2013, 42 (06) : 2243 - 2285
  • [33] ON THE ANGULAR RESOLUTION OF PLANAR GRAPHS
    MALITZ, S
    PAPAKOSTAS, A
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1994, 7 (02) : 172 - 183
  • [34] Diameter bounds for planar graphs
    Fulek, Radoslav
    Moric, Filip
    Pritchard, David
    [J]. DISCRETE MATHEMATICS, 2011, 311 (05) : 327 - 335
  • [35] Extending Colorings of Planar Graphs
    Lu, Weihua
    Ren, Han
    [J]. GRAPHS AND COMBINATORICS, 2019, 35 (05) : 1161 - 1167
  • [36] Combinatorial curvature for planar graphs
    Higuchi, Y
    [J]. JOURNAL OF GRAPH THEORY, 2001, 38 (04) : 220 - 229
  • [37] Acyclic edge colorings of planar graphs and seriesparallel graphs
    JianFeng Hou
    JianLiang Wu
    GuiZhen Liu
    Bin Liu
    [J]. Science in China Series A: Mathematics, 2009, 52 : 605 - 616
  • [38] PLANAR AND PROJECTIVE LINE GRAPHS OF COMAXIMAL GRAPHS OF LATTICES
    Afkhami, Mojgan
    Khashyarmanesh, Kazem
    Parsapour, Atossa
    [J]. INTERNATIONAL ELECTRONIC JOURNAL OF ALGEBRA, 2014, 16 : 72 - 88
  • [39] Acyclic edge colorings of planar graphs and seriesparallel graphs
    Hou JianFeng
    Wu JianLiang
    Liu GuiZhen
    Liu Bin
    [J]. SCIENCE IN CHINA SERIES A-MATHEMATICS, 2009, 52 (03): : 605 - 616
  • [40] Disk embeddings of planar graphs
    Chen, ZZ
    He, X
    [J]. ALGORITHMICA, 2004, 38 (04) : 539 - 576
12345