✦ LIBER ✦

Efficient minus and signed domination in graphs

✍ Scribed by Chin Lung Lu; Sheng-Lung Peng; Chuan Yi Tang

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 399 KB
Volume: 301
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(02)00594-7

No coin nor oath required. For personal study only.

✦ Synopsis

An e cient minus (respectively, signed) dominating function of a graph G = (V; E) is a function f :

The e cient minus (respectively, signed) domination problem is to ÿnd an e cient minus (respectively, signed) dominating function of G. In this paper, we show that the e cient 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 e cient minus (respectively, signed) dominating function. We also give linear-time algorithms to ÿnd these functions. Besides, we show that the e cient minus domination problem is equivalent to the e cient domination problem on trees.

📜 SIMILAR VOLUMES

Minus domination in graphs

✍ Jean Dunbar; Stephen Hedetniemi; Michael A. Henning; Alice McRae 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 787 KB

Minus domination in regular graphs

✍ Jean Dunbar; Stephen Hedetniemi; Michael A. Henning; Alice A. McRae 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 77 KB

Signed domination in regular graphs

✍ Odile Favaron 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 456 KB

In answer to the open questions proposed by Henning and Slater, we give sharp upper bounds on the upper signed domination number of a regular graph and on the signed domination number of a connected cubic graph. Let G = (V, E) be a simple graph. For v E V, we denote by d(u) the degree of v in V, by

Signed Domination in Regular Graphs and

Signed Domination in Regular Graphs and Set-Systems

✍ Zoltán Füredi; Dhruv Mubayi 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 188 KB

Suppose G is a graph on n vertices with minimum degree r. Using standard random methods it is shown that there exists a two-coloring of the vertices of G with colors, +1 and &1, such that all closed neighborhoods contain more 1's than &1's, and all together the number of 1's does not exceed the numb

Generalized domination and efficient dom

Generalized domination and efficient domination in graphs

✍ D.W. Bange; A.E. Barkauskas; L.H. Host; P.J. Slater 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 516 KB

This paper generalizes dominating and efficient dominating sets of a graph. Let G be a graph with vertex set V(G). If f: V(G) ~ Y, where Y is a subset of the reals, the weight off is the sum of f(v) over all ve V(G). If the closed neighborhood sum off(v) at every vertex is at least 1, thenfis called

The algorithmic complexity of minus domi

The algorithmic complexity of minus domination in graphs

✍ Jean Dunbar; Wayne Goddard; Stephen Hedetniemi; Alice McRae; Michael A. Henning 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 796 KB