# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

# Discussiones Mathematicae Graph Theory

## ALGORITHMIC ASPECTS OF TOTAL-SUBDOMINATION IN GRAPHS

1Laura M. Harris, 2Johannes H. Hattingh and 1Michael A. Henning

1School of Mathematical Sciences
University of KwaZulu-Natal
Pietermaritzburg, 3209 South Africa

2Department of Mathematics and Statistics
Georgia State University
Atlanta, GA 30303-3083 USA
e-mail: jhhattingh@gsu.edu

## 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.

Keywords: total k-subdomination, algorithm, tree.

2000 Mathematics Subject Classification: 05C69.

## References

  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.  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.  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.  E.J. Cockayne and C. Mynhardt, On a generalisation of signed dominating functions of graphs, Ars Combin. 43 (1996) 235-245.  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.  O. Favaron, Signed domination in regular graphs, Discrete Math. 158 (1996) 287-293, doi: 10.1016/0012-365X(96)00026-X.  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.  M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979).  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.  L. Harris, J.H. Hattingh and M.A. Henning, Total k-subdominating functions on graphs, submitted for publication.  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.  M.A. Henning, Domination in regular graphs, Ars Combin. 43 (1996) 263-271.  M.A. Henning, Dominating functions in graphs, Domination in Graphs: Volume II (Marcel-Dekker, Inc., 1998) 31-62.  M.A. Henning, Signed total domination in graphs, to appear in Discrete Math.  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.  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.  P. Lam and B. Wei, On the total domination number of graphs, submitted for publication.  J. Matousek, On the signed domination in graphs, Combinatoria 20 (2000) 103-108, doi: 10.1007/s004930070034.  X. Yang, X. Huang and Q. Hou, On graphs with equal signed and majority domination number, manuscript (personal communication by X. Yang).  H. Yeh and G.J. Chang, Algorithmic aspects of majority domination, Taiwanese J. Math. 1 (1997) 343-350.  B. Zelinka, Some remarks on domination in cubic graphs, Discrete Math. 158 (1996) 249-255, doi: 10.1016/0012-365X(94)00324-C.  B. Zelinka, Signed total domination number of a graph, Czechoslovak Math. J. 51 (2001) 225-229, doi: 10.1023/A:1013782511179.  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.