×

Dominating functions with integer values in graphs — a survey. (English) Zbl 1155.05333

Summary: For an arbitrary subset \(P\) of the reals, a function \(f: V\to P\) is defined to be a \(P\)-dominating function of a graph \(G=(V,E)\) if the sum of its function values over any closed neighborhood is at least 1. That is, for every \(v\in V\), \(f(N[v])\geqslant1\). The definition of total \(P\)-dominating function is obtained by simply changing ‘closed’ neighborhood \(N[v]\) in the definition of \(P\)-dominating function to ‘open’ neighborhood \(N(v)\). The (total) \(P\)-domination number of a graph \(G\) is defined to be the infimum of weight \(w(f)=\sum_{v\in V} f(v)\) taken over all (total) \(P\)-dominating function \(f\). Similarly, the \(P\)-edge and \(P\)-star dominating functions can be defined. In this paper we survey some recent progress on the topic of dominating functions in graph theory. Especially, we are interested in \(P\)-, \(P\)-edge and \(P\)-star dominating functions of graphs with integer values.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Haynes T W, Hedetniemi S T, Slater P J. Fundamentals of Domination in Graphs [M]. New York: Marcel Dekker, 1998. · Zbl 0890.05002
[2] Haynes T W, Hedetniemi S T, Slater P J. Domination in Graphs: Advanced Topics [M]. New York: Marcel Dekker, 1998. · Zbl 0883.00011
[3] Bange D W, Barkauskas A E, Host L H, Slater P J. Generalized domination and efficient domination in graphs [J]. Discrete Mathematics, 1996, 159: l–11. · Zbl 0860.05044 · doi:10.1016/0012-365X(95)00094-D
[4] Domke G S, Fricke G H, Laskar R R, Majumdar A. Fractional domination and related parameters [M]// Domination in Graphs. New York: Marcel Dekker, 1998. · Zbl 0894.05027
[5] Dunbar J E, Hedetniemi S T, Henning M A, McRae A A. Minus domination in graphs [J]. Discrete Mathematics, 1999, 199: 35–47. · Zbl 0928.05046 · doi:10.1016/S0012-365X(98)00284-2
[6] Dunbar J E, Hedetniemi S T, Henning M A, Slater P J. Signed domination in graphs [M]// Graph Theory, Combinatorics, and Applications: Vol. 1. New York: Wiley, 1995: 311–322. · Zbl 0842.05051
[7] Henning M A. Dominating function in graphs [M]// Domination in Graphs: Advanced Topics: Vol.II. New York: Marcel Dekker Inc., 1998: 31–62. · Zbl 0891.05044
[8] Harris L, Hattingh J H. The algorithm complexity of certain functional variations of total domination in graphs [J]. Australasian Journal of Combinatorics, 2004, 29: 143–156. · Zbl 1084.05049
[9] Zelinka B. Signed total domination number of a graph [J]. Czechoslovak Mathematical Journal, 2001, 51: 225–229. · Zbl 0977.05096 · doi:10.1023/A:1013782511179
[10] Cockayne E J, Mynhardt C M. On a generalization of signed dominating function of graphs [J]. Ars Combinatoria, 1996, 43: 235–245. · Zbl 0881.05060
[11] Broere I, Hattingh J H, Henning M A, McRae A A. Majority domination in graphs [J]. Discrete Mathematics, 1995, 138: 125–135. · Zbl 0820.05037 · doi:10.1016/0012-365X(94)00194-N
[12] Beineke L, Henning M A. Opinion function in graphs [J]. Discrete Mathematics, 1997, 167: 167–178. · Zbl 0883.05039 · doi:10.1016/S0012-365X(96)00221-X
[13] Hattingh J H, Ungerer E. Minus k-subdomination in graphs II [J]. Discrete Mathematics, 1997, 171: 141–151. · Zbl 0876.05043 · doi:10.1016/S0012-365X(96)00003-9
[14] Chen W D, Song E M. Lower bounds on several versions of signed domination number [J]. Discrete Mathematics, 2007. doi: 10.1016/j.disc.2006.09.050. · Zbl 1168.05343
[15] Damaschke P. Minus domination in small-degree graphs [J]. Discrete Applied Mathematics, 2001, 108: 53–64. · Zbl 0971.05086 · doi:10.1016/S0166-218X(00)00219-5
[16] Favaron O. Signed domination in regular graphs [J]. Discrete Mathematics, 1996, 158: 287–293. · Zbl 0861.05033 · doi:10.1016/0012-365X(96)00026-X
[17] Füredi Z, Mubayi D. Signed domination in regular graphs and set-systems [J]. Journal of Combinatorial Theory, Series B, 1999, 76: 223–239. · Zbl 0933.05117 · doi:10.1006/jctb.1999.1905
[18] Hattingh J H, Henning M A, Slater P J. The algorithmic complexity of signed domination in graphs [J]. Australasian Journal of Combinatorics, 1995, 12: 101–112. · Zbl 0835.68089
[19] Henning M A. Domination in regular graphs [J]. Ars Combinatoria, 1996, 43: 263–271. · Zbl 0881.05101
[20] Henning M A, Slater P J. Inequalities relating domination parameters in cubic graphs [J]. Discrete Mathematics, 1996, 158: 87–98. · Zbl 0858.05058 · doi:10.1016/0012-365X(96)00025-8
[21] Kang L Y, Shan E F. Lower bounds on domination function in graphs [J]. Ars Combinatoria, 2000, 56: 121–128. · Zbl 0994.05105
[22] Shan E F, Cheng T C E, Kang L Y. An application of Turán theorem to domination in graphs [J]. Discrete Applied Mathematics, submitted.
[23] Shan E F, Sohn M Y, Kang L Y. Upper bounds on signed 2-independence number of graphs [J]. Ars Combinatoria, 2003, 169: 229–239. · Zbl 1073.05559
[24] Tang H J, Chen Y J. A note on the signed domination number of graphs [J]. Discrete Mathematics, 2007. doi: 10.1016/j.disc.2007.06.031.
[25] Wang C X, Mao J Z. A proof of a conjecture of minus domination in graphs [J]. Discrete Mathematics, 2002, 256: 519–521. · Zbl 1008.05114 · doi:10.1016/S0012-365X(01)00316-8
[26] Xu B G. On signed domination and minus domination in graphs [J]. Journal of Mathematical Research and Exposition, 2003, 23(4): 586–590. · Zbl 1049.05061
[27] Zhang Z F, Xu B G, Li Y Z, Liu L Z. A note on the lower bounds of signed domination number of a graph [J]. Discrete Mathematics, 1999, 195: 295–298. · Zbl 0928.05052 · doi:10.1016/S0012-365X(98)00189-7
[28] Haas R, Wexler T B. Bounds on the signed domination number of a graph [J]. Electronic Notes in Discrete Mathematics, 2002, 11: 742–750. · Zbl 1075.05577 · doi:10.1016/S1571-0653(04)00118-0
[29] Zelinka B. Some remarks on domination in cubic graphs [J]. Discrete Mathematics, 1996, 158: 249–255. · Zbl 0861.05034 · doi:10.1016/0012-365X(94)00324-C
[30] Wang H C, Shan E F. Signed total 2-independence in graphs [J]. Utilitas Mathematica (to appear). · Zbl 1183.05062
[31] Henning M A. Signed total domination in graphs [J]. Discrete Mathematics, 2004, 278: 109–125. · Zbl 1036.05035 · doi:10.1016/j.disc.2003.06.002
[32] Shan E F, Cheng T C E. Remarks on the minus (signed) total domination in graphs [J]. Discrete Mathematics, 2007. doi: 10.1016/j.disc.2007.06.015. · Zbl 1169.05367
[33] Turán P. On an extremal problemin graph theory [J]. Math. Fiz. Lapok, 1941, 48: 436–452.
[34] Kang L Y, Shan E F. Signed total domination in nearly regular graphs [J]. Journal of Shanghai University (English Edition), 2006, 10(1): 4–8. · Zbl 1118.05074 · doi:10.1007/s11741-006-0097-3
[35] Gao M J, Shan E F. The signed total domination number of graphs [J]. Ars Combinatoria (to appear). · Zbl 1249.05283
[36] Shi W, Wang H C, Kang L Y. Upper bounds of algebraic connectivity related to total domination in graphs [J]. Linear Algebra and Its Applications, submitted.
[37] Hattingh J H, Ungerer E. The signed and minus k-subdomination numbers of comets [J]. Discrete Mathematics, 1998, 183: 141–152. · Zbl 0893.05005 · doi:10.1016/S0012-365X(97)00051-4
[38] Chang G J, Liaw S C, Yeh H G. k-subdomination in graphs [J]. Discrete Applied Mathematics, 2002, 120: 55–60. · Zbl 1008.05110 · doi:10.1016/S0166-218X(01)00280-3
[39] Kang L Y, Qiao H, Shan E F, Du D Z. Lower bounds on the minus domination and k-subdomination numbers [J]. Theoretical Computer Science, 2003, 296: 89–98. · Zbl 1046.68078 · doi:10.1016/S0304-3975(02)00434-6
[40] Kang L Y, Dang C Y, Cai M C, Shan E F. Upper minus domination for k-subdomination number of graphs [J]. Discrete Mathematics, 2002, 247: 229–234. · Zbl 0990.05098 · doi:10.1016/S0012-365X(01)00311-9
[41] Henning M A, Hind H R. Strict majority functions on graphs [J]. Journal of Graph Theory, 1998, 28: 49–56. · Zbl 0919.05032 · doi:10.1002/(SICI)1097-0118(199805)28:1<49::AID-JGT6>3.0.CO;2-F
[42] Holm T S. On majority domination in graphs [J]. Discrete Mathematics, 2001, 239: 1–12. · Zbl 0982.05072 · doi:10.1016/S0012-365X(00)00370-8
[43] Xing H M, Sun L. On signed majority total domination in graphs [J]. Czechoslovak Mathematical Journal, 2005, 55(130): 341–348. · Zbl 1081.05049 · doi:10.1007/s10587-005-0025-x
[44] Xing H M, Sun L, Chen X G. On a generalization of signed total dominating functions of graphs [J]. Ars Combinatoria, 2005, 77: 205–215. · Zbl 1164.05426
[45] Dunbar J E, Hedetniemi S T, Goddard W, McRae A A, Henning M A. The algorithmic complexity of minus domination in graphs [J]. Discrete Applied Mathematics, 1996, 68: 73–84. · Zbl 0848.05041 · doi:10.1016/0166-218X(95)00056-W
[46] Chen Y J, Cheng T C E, Ng C T, Shan E F. A note on domination and minus domination numbers in cubic graphs [J]. Applied Mathematics Letters, 2005, 18: 1062–1067. · Zbl 1082.05067 · doi:10.1016/j.aml.2004.11.003
[47] Dunbar J E, Hedetniemi S T, Henning M A, McRae A A. Minus domination in regular graphs [J]. Discrete Mathematics, 1996, 149: 311–312. · Zbl 0843.05059 · doi:10.1016/0012-365X(94)00329-H
[48] Matoušek J. Lower bound on the minus-domination number [J]. Discrete Mathematics, 2001, 233: 361–370. · Zbl 0986.05081 · doi:10.1016/S0012-365X(00)00252-1
[49] Liu H L, Sun L. On the minus domination number of graphs [J]. Czechoslovak Mathematical Journal, 2004, 54(129): 883–887. · Zbl 1080.05523 · doi:10.1007/s10587-004-6437-1
[50] Wang C X, Mao J Z. A proof of a conjecture of minus domination in graphs [J]. Discrete Mathematics, 2002, 256: 519–521. · Zbl 1008.05114 · doi:10.1016/S0012-365X(01)00316-8
[51] Kang L Y, Kim H K, Sohn M Y. Minus domination number in k-partite graphs [J]. Discrete Mathematics, 2004, 277: 295–300. · Zbl 1033.05077 · doi:10.1016/j.disc.2003.07.008
[52] Kang L Y, Cai M C. Minus domination number in cubic graphs [J]. Chinese Science Bulletin, 1998, 6: 444–447. · Zbl 0986.05083 · doi:10.1007/BF02883804
[53] Kang L Y, Cai M C. Upper minus domination in regular graphs [J]. Discrete Mathematics, 2000, 219: 135–144. · Zbl 0948.05039 · doi:10.1016/S0012-365X(99)00245-9
[54] Shang W P, Yuan J J. Upper minus domination in a claw-free cubic graph [J]. Discrete Mathematics, 2006, 306: 2983–2988. · Zbl 1106.05072 · doi:10.1016/j.disc.2005.09.050
[55] Lee J, Sohn M Y, Kim H K. A note on graphs with large girth and small minus domination number [J]. Discrete Applied Mathematics, 1999, 91: 299–303. · Zbl 0918.05070 · doi:10.1016/S0166-218X(98)00082-1
[56] Xu G J, Shan E F, Kang L Y, Cheng T C E. The algorithmic complexity of the minus clique-transversal problem [J]. Applied Mathematics and Computation, 2007, 189: 1410–1418. · Zbl 1125.05076 · doi:10.1016/j.amc.2006.12.027
[57] Kang L Y, Shan E F, Caccetta L. Total minus domination in k-partite graphs [J]. Discrete Mathematics, 2006, 306: 1771–1775. · Zbl 1101.05048 · doi:10.1016/j.disc.2006.03.004
[58] Yan H, Yang X Q, Shan E F. Upper minus total domination in small-degree regular graphs [J]. Discrete Mathematics, 2007. doi:10.1016/j.disc.2006.11.011. · Zbl 1125.05077
[59] Wang H C, Shan E F. Upper minus total domination of a 5-regular graph [J]. Ars Combinatoria (to appear). · Zbl 1224.05386
[60] Broere I, Dunbar J E, Hattingh J H. Minus ksubdomination in graphs [J]. Ars Combinatoria, 1998, 50: 177–186. · Zbl 0963.05099
[61] Hattingh J H, McRae A A, Ungerer E. Minus ksubdomination in graphs III [J]. Australasian Journal of Combinatorics, 1998, 17: 69–76. · Zbl 0903.05027
[62] Lu C L, Peng S L, Tang C Y. Effcient minus and signed domination in graphs [J]. Theoretical Computer Science, 2003, 301: 381–397. · Zbl 1022.68103 · doi:10.1016/S0304-3975(02)00594-7
[63] Garey M R, Johnson D S. Computers and Intractability–A Guide to the Theory of NP-Completeness [M]. San Francisco, CA: Freeman, 1979. · Zbl 0411.68039
[64] Xu B G. On signed edge domination numbers of graphs [J]. Discrete Mathematics, 2001, 239: 179–189. · Zbl 0979.05081 · doi:10.1016/S0012-365X(01)00044-9
[65] Xu B G. On edge domination numbers of graphs [J]. Discrete Mathematics, 2005, 294: 311–316. · Zbl 1062.05116 · doi:10.1016/j.disc.2004.11.008
[66] Xu B G. Two classes of edge domination in graphs [J]. Discrete Applied Mathematics, 2006, 154: 1541–1546. · Zbl 1091.05055 · doi:10.1016/j.dam.2005.12.007
[67] Wang C P. The signed star domination numbers of the Cartesian product graphs [J]. Discrete Applied Mathematics, 2007, 155: 1497–1505. · Zbl 1119.05085 · doi:10.1016/j.dam.2007.04.008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.