Name
Abstract | ||
|---|---|---|
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 Σu∈M[v] f(u) = 1 for all v ∈ V, where N[v] = {v} ∪ {u|(u,v) ∈ 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. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0304-3975(02)00594-7 | Theoretical Computer Science |
Keywords | Field | DocType |
interval graph,efficient minus,domination problem,planar bipartite graph,graph G,chordal graph,chordal bipartite graph,dominating function,efficient domination problem,efficient minus domination problem | Discrete mathematics,Combinatorics,Indifference graph,Interval graph,Chordal graph,Clique-sum,Treewidth,Pathwidth,Mathematics,Split graph,Maximal independent set | Journal |
Volume | Issue | ISSN |
301 | 1-3 | Theoretical Computer Science |
ISBN | Citations | PageRank |
3-540-41255-7 | 1 | 0.37 |
References | Authors | |
8 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chin Lung Lu | 1 | 423 | 34.59 |
| Sheng-lung Peng | 2 | 173 | 20.25 |
| Chuan Yi Tang | 3 | 704 | 79.25 |
| CL Lu | 4 | 1 | 0.37 |
| SL Peng | 5 | 1 | 0.37 |
| CY Tang | 6 | 1 | 0.37 |