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

共 16 条

[1]

Brandstadt A., 1999, GRAPH CLASSES SURVEY

[2]

DAHLHAUS E, 1994, LECT NOTES COMPUTER, V903, P81

[3]

Dirac G. A., 1961, Abh. Math. Semin. Univ. Hambg, V25, P71, DOI [10.1007/BF02992776, DOI 10.1007/BF02992776]

[4] Weakly triangulated comparability graphs [J].