標題: Efficient minus and signed domination in graphs
作者: Lu, CL
Peng, SL
Tang, CY
生物科技學系
Department of Biological Science and Technology
關鍵字: efficient minus domination;efficient signed domination;chordal graphs;chordal bipartite graphs;planar bipartite graphs;chain interval graphs
公開日期: 14-May-2003
摘要: An efficient minus (respectively, signed) dominating function of a graph G = (V,E) is a function f:V --> {-1,0,1} (respectively, {-1,1}) such that Sigma(uis an element ofN[nu]) f(u) = I for all nu is an element of V, where N [nu] = {nu} boolean OR {u (u, nu) is an element of E}. The efficient minus (respectively, signed) domination problem is to find an efficient minus (respectively, signed) dominating function of G. In this paper, we show that the efficient minus (respectively, signed) domination problem is NP-complete on chordal graphs, chordal bipartite graphs, planar bipartite graphs and planar graphs of maximum degree 4 (respectively, on chordal graphs). Based on the forcing property on blocks of vertices and automata theory, we provide a uniform approach to show that in a special class of interval graphs, every graph (respectively, every graph with no vertex of odd degree) has an efficient minus (respectively, signed) dominating function. We also give linear-time algorithms to find these functions. Besides, we show that the efficient minus domination problem is equivalent to the efficient domination problem on trees. (C) 2002 Elsevier Science B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/S0304-3975(02)00594-7
http://hdl.handle.net/11536/27870
ISSN: 0304-3975
DOI: 10.1016/S0304-3975(02)00594-7
期刊: THEORETICAL COMPUTER SCIENCE
Volume: 301
Issue: 1-3
起始頁: 381
結束頁: 397
Appears in Collections:Articles


Files in This Item:

  1. 000182912100018.pdf