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 条
[41]   KNOTTED PROJECTIONS OF PLANAR GRAPHS [J].
TANIYAMA, K .
PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1995, 123 (11) :3575-3579
[42]   Angles of planar triangular graphs [J].
DiBattista, G ;
Vismara, L .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1996, 9 (03) :349-359
[43]   Minimum choosability of planar graphs [J].
Wang, Huijuan ;
Liu, Bin ;
Gai, Ling ;
Du, Hongwei ;
Wu, Jianliang .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 36 (01) :13-22
[44]   Equitable partition of planar graphs [J].
Kim, Ringi ;
Oum, Sang-il ;
Zhang, Xin .
DISCRETE MATHEMATICS, 2021, 344 (06)
[45]   Venn diagrams and planar graphs [J].
Chilakamarri, KB ;
Hamburger, P ;
Pippert, RE .
GEOMETRIAE DEDICATA, 1996, 62 (01) :73-91
[46]   On the Queue Number of Planar Graphs [J].
Di Battista, Giuseppe ;
Frati, Fabrizio ;
Pach, Janos .
2010 IEEE 51ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2010, :365-374
[47]   Rectangular drawings of planar graphs [J].
Rahman, MS ;
Nishizeki, T ;
Ghosh, S .
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2004, 50 (01) :62-78
[48]   Planar character-graphs [J].
Ebrahimi, Mahdi ;
Khatami, Maryam ;
Mirzaei, Zohreh .
COMMUNICATIONS IN ALGEBRA, 2021, 49 (09) :4079-4087
[49]   Packing trees into planar graphs [J].
García, A ;
Hernando, C ;
Hurtado, F ;
Noy, M ;
Tejel, J .
JOURNAL OF GRAPH THEORY, 2002, 40 (03) :172-181
[50]   Injective coloring of planar graphs [J].
Bu, Yuehua ;
Chen, Dong ;
Raspaud, Andre ;
Wang, Weifan .
DISCRETE APPLIED MATHEMATICS, 2009, 157 (04) :663-672
12345