AUTHORS: Radosław Ziemann
Download as PDF
: In this paper we claim that the Corollary 2 in [V. Pinciu, Dominating sets for outerplanar graphs, WSEAS Transactions on Mathematics 1(3), 2004, pp. 55–58] is false. In particular, we present a linear-time algorithm for partial k-trees that solves the problem.
KEYWORDS: Algorithm, connected domination, linear-time, partial k-trees
REFERENCES:
[
1] R. E. Bellman, S. E. Dreyfus, Applied Dynamic
Programming, Princeton University Press, 1962.
[2] H. L. Bodlaender, A linear-time algorithm for
finding tree-decompositions of small treewidth.
SIAM J. Comput. 25(6), 1996. pp. 1305-1317.
[3] H. L. Bodlaender, Dynamic programming on
graphs with bounded treewidth, International
Colloquium on Automata, Languages, and Programming, 1988, pp. 105–118.
[4] B. Courcelle, The monadic second-order logic of
graphs. I. Recognizable sets of finite graphs, Inf.
Comput. 85(1), 1990, pp. 12–75.
[5] W. J. Desormeaux, T. W. Haynes, M. A. Henning, Bounds on the connected domination number of a graph, Discrete Appl. Math. 161(18),
2013, pp. 2925–2931.
[6] R. Diestel, Graph Theory, Springer, Heidelberg,
2012.
[7] W. Duckworth, B. Mansb, Connected domination of regular graphs, Discrete Math. 309(8),
2009, pp. 2305–2322.
[8] M. Frick, M. Grohe, The complexity of firstorder and monadic second-order logic revisited,
Ann. Pure Appl. Logic 130(13), 2004, pp. 3–31.
[9] H. Karami, A. Khodkar, S. M. Sheikholeslami,
D. B. West, Connected domination number of
a graph and its complement, Graphs Combin.
28(1), 2012, pp. 123–131.
[10] M. Lema ´nska, E. Rivera-Campo, R. Ziemann,
R. Zuazua, P. Zyli ´nski, Convex dominating sets ˙
in maximal outerplanar Graphs, Discrete Appl.
Math. 265, 2019, pp. 142–157.
[11] V. Pinciu, Dominating sets for outerplanar
graphs, WSEAS Transactions on Mathematics
1(3), 2004, pp. 55–58.
[12] D. Rose, G. Lueker, R. E. Tarjan, Algorithmic
aspects of vertex elimination on graphs. SIAM J.
Comput. 5(2), 1976, pp. 266–283.
[13] N. Robertson, P. D. Seymour, Graph minors. II.
Algorithmic aspects of treewidth, J. Algorithms
7, 1986, pp. 309–322.
[14] E. Sampathkumar, H. B. Walikar, The connected
domination number of a graph, J. Math. Phys.
Sci. 13(6), 1979, pp. 607–613.
[15] M. Sysło, Characterizations of outerplanar
graphs, Discrete Math. 26(1), 1979, pp. 47–53.
[16] J. A. Telle, A. Proskurowski, Practical algorithms on partial k-trees with an application to
domination-like problems, Workshop on Algorithms and Data Structures, 1993, pp. 610–621.
