Algorithmic aspects of total-subdomination in graphs

Laura M. Harris; Johannes H. Hattingh; Michael A. Henning

Discussiones Mathematicae Graph Theory (2006)

  • Volume: 26, Issue: 1, page 5-18
  • ISSN: 2083-5892

Abstract

top
Let G = (V,E) be a graph and let k ∈ Z⁺. A total k-subdominating function is a function f: V → {-1,1} such that for at least k vertices v of G, the sum of the function values of f in the open neighborhood of v is positive. The total k-subdomination number of G is the minimum value of f(V) over all total k-subdominating functions f of G where f(V) denotes the sum of the function values assigned to the vertices under f. In this paper, we present a cubic time algorithm to compute the total k-subdomination number of a tree and also show that the associated decision problem is NP-complete for general graphs.

How to cite

top

Laura M. Harris, Johannes H. Hattingh, and Michael A. Henning. "Algorithmic aspects of total-subdomination in graphs." Discussiones Mathematicae Graph Theory 26.1 (2006): 5-18. <http://eudml.org/doc/270679>.

@article{LauraM2006,
abstract = {Let G = (V,E) be a graph and let k ∈ Z⁺. A total k-subdominating function is a function f: V → \{-1,1\} such that for at least k vertices v of G, the sum of the function values of f in the open neighborhood of v is positive. The total k-subdomination number of G is the minimum value of f(V) over all total k-subdominating functions f of G where f(V) denotes the sum of the function values assigned to the vertices under f. In this paper, we present a cubic time algorithm to compute the total k-subdomination number of a tree and also show that the associated decision problem is NP-complete for general graphs.},
author = {Laura M. Harris, Johannes H. Hattingh, Michael A. Henning},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {total k-subdomination; algorithm; tree; total domination; majority domination; signed domination},
language = {eng},
number = {1},
pages = {5-18},
title = {Algorithmic aspects of total-subdomination in graphs},
url = {http://eudml.org/doc/270679},
volume = {26},
year = {2006},
}

TY - JOUR
AU - Laura M. Harris
AU - Johannes H. Hattingh
AU - Michael A. Henning
TI - Algorithmic aspects of total-subdomination in graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2006
VL - 26
IS - 1
SP - 5
EP - 18
AB - Let G = (V,E) be a graph and let k ∈ Z⁺. A total k-subdominating function is a function f: V → {-1,1} such that for at least k vertices v of G, the sum of the function values of f in the open neighborhood of v is positive. The total k-subdomination number of G is the minimum value of f(V) over all total k-subdominating functions f of G where f(V) denotes the sum of the function values assigned to the vertices under f. In this paper, we present a cubic time algorithm to compute the total k-subdomination number of a tree and also show that the associated decision problem is NP-complete for general graphs.
LA - eng
KW - total k-subdomination; algorithm; tree; total domination; majority domination; signed domination
UR - http://eudml.org/doc/270679
ER -

References

top
  1. [1] L.W. Beineke and M.A. Henning, Opinion function on trees, Discrete Math. 167-168 (1997) 127-139, doi: 10.1016/S0012-365X(96)00221-X. 
  2. [2] I. Broere, J.H. Hattingh, M.A. Henning and A.A. McRae, Majority domination in graphs, Discrete Math. 138 (1995) 125-135, doi: 10.1016/0012-365X(94)00194-N. Zbl0820.05037
  3. [3] G. Chang, S.C. Liaw and H.G. Yeh, k-subdomination in graphs, Discrete Applied Math. 120 (2002) 55-60, doi: 10.1016/S0166-218X(01)00280-3. Zbl1008.05110
  4. [4] E.J. Cockayne and C. Mynhardt, On a generalisation of signed dominating functions of graphs, Ars Combin. 43 (1996) 235-245. Zbl0881.05060
  5. [5] J.E. Dunbar, S.T. Hedetniemi, M.A. Henning and P.J. Slater, Signed domination in graphs, Graph Theory, Combinatorics and Applications, John Wiley & Sons, Inc. 1 (1995) 311-322. Zbl0842.05051
  6. [6] O. Favaron, Signed domination in regular graphs, Discrete Math. 158 (1996) 287-293, doi: 10.1016/0012-365X(96)00026-X. Zbl0861.05033
  7. [7] Z. Furedi and D. Mubayi, Signed domination in regular graphs and set-systems, J. Combin. Theory (B) 76 (1999) 223-239, doi: 10.1006/jctb.1999.1905. Zbl0933.05117
  8. [8] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979). Zbl0411.68039
  9. [9] L. Harris and J.H. Hattingh, The algorithmic complexity of certain functional variations of total domination in graphs, Australasian J. Combin. 29 (2004) 143-156. Zbl1084.05049
  10. [10] L. Harris, J.H. Hattingh and M.A. Henning, Total k-subdominating functions on graphs, submitted for publication. Zbl1097.05031
  11. [11] J.H. Hattingh, M.A. Henning and P.J. Slater, The algorithmic complexity of signed domination in graphs, Australasian J. Combin. 12 (1995) 101-112. Zbl0835.68089
  12. [12] M.A. Henning, Domination in regular graphs, Ars Combin. 43 (1996) 263-271. Zbl0881.05101
  13. [13] M.A. Henning, Dominating functions in graphs, Domination in Graphs: Volume II (Marcel-Dekker, Inc., 1998) 31-62. Zbl0891.05044
  14. [14] M.A. Henning, Signed total domination in graphs, to appear in Discrete Math. 
  15. [15] M.A. Henning and H. Hind, Strict open majority functions in Graphs, J. Graph Theory 28 (1998) 49-56, doi: 10.1002/(SICI)1097-0118(199805)28:1<49::AID-JGT6>3.0.CO;2-F Zbl0919.05032
  16. [16] M.A. Henning and P.J. Slater, Inequalities relating domination parameters in cubic graphs, Discrete Math. 158 (1996) 87-98, doi: 10.1016/0012-365X(96)00025-8. Zbl0858.05058
  17. [17] P. Lam and B. Wei, On the total domination number of graphs, submitted for publication. 
  18. [18] J. Matousek, On the signed domination in graphs, Combinatoria 20 (2000) 103-108, doi: 10.1007/s004930070034. Zbl0949.05058
  19. [19] X. Yang, X. Huang and Q. Hou, On graphs with equal signed and majority domination number, manuscript (personal communication by X. Yang). 
  20. [20] H. Yeh and G.J. Chang, Algorithmic aspects of majority domination, Taiwanese J. Math. 1 (1997) 343-350. Zbl0882.05114
  21. [21] B. Zelinka, Some remarks on domination in cubic graphs, Discrete Math. 158 (1996) 249-255, doi: 10.1016/0012-365X(94)00324-C. Zbl0861.05034
  22. [22] B. Zelinka, Signed total domination number of a graph, Czechoslovak Math. J. 51 (2001) 225-229, doi: 10.1023/A:1013782511179. Zbl0977.05096
  23. [23] Z. Zhang, B. Xu, Y. Li and L. Liu, A note on the lower bounds of signed domination number of a graph, Discrete Math. 195 (1999) 295-298, doi: 10.1016/S0012-365X(98)00189-7. Zbl0928.05052

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.