Abstract
In 1985, Fink and Jacobson gave a generalization of the concepts of domination and independence in graphs. For a positive integer k, a subset S of vertices in a graph G = (V, E) is k-dominating if every vertex of V − S is adjacent to at least k vertices in S. The subset S is k-independent if the maximum degree of the subgraph induced by the vertices of S is less or equal to k − 1. In this paper we survey results on k-domination and k-independence.
Similar content being viewed by others
References
Allan R.B., Laskar R.: On domination and independent domination numbers of a graph. Discrete Math. 23, 73–76 (1978)
Alon N.: Transversal numbers of uniform hypergraphs. Graphs Combin. 6, 1–4 (1990)
Alon, N., Spencer, J.: The Probabilistic Method. In: Wiley-Interscience Series in Discrete Mathematics and Optimization, 2nd edn. Wiley-Interscience, New York (2000, with an appendix on the life and work of Paul Erdős)
Araki T.: On the k-tuple domination of de Bruijn and Kautz digraphs. Inform. Process. Lett. 104, 86–90 (2007)
Arnautov V.I.: Estimation of the exterior stability number of a graph by means of the minimal degree of vertices. Prikl. Mat. i Programmirovanie 11, 3–8 (1974) (in Russian)
Atapour M., Sheikholeslami S.M., Hansberg A., Volkmann L., Khodkar A.: 2-domination subdivision number of graphs. AKCE J. Graphs Combin. 5, 169–177 (2008)
Bange D.W., Barkauskas A.E., Slater P.J.: A constructive characterization of trees with two disjoint minimum dominating sets. Congr. Numer. 21, 101–112 (1978)
Bean T.J., Henning M.A., Swart H.C.: On the integrity of distance domination in graphs. Australas. J. Combin. 10, 29–43 (1994)
Berge C.: Les problèmes de coloration en théorie des graphes. Publ. Inst. Stat. Univ. Paris 9, 123–160 (1960)
Blidia, M., Bouchou, A., Volkmann, L.: Bounds on the k-independence and k-chromatic numbers of graphs. Ars Combin (in press)
Blidia M., Chellali M., Favaron O.: Independence and 2-domination in trees. Australas. J. Combin. 33, 317–327 (2005)
Blidia, M., Chellali, M., Favaron, O.: Ratios of some domination parameters in graphs and claw-free graphs. In: Graph Theory, Trends in Mathematics, pp. 61–72. Birkhäuser, Basel (2006)
Blidia M., Chellali M., Favaron O., Meddah N.: On k-independence in graphs with emphasis on trees. Discrete Math. 307, 2209–2216 (2007)
Blidia M., Chellali M., Favaron O., Meddah N.: Maximal k-independent sets in graphs. Discuss. Math. Graph Theory 28, 151–163 (2008)
Blidia M., Chellali M., Haynes T.W.: Characterizations of trees with equal paired and double domination numbers. Discrete Math. 306, 1840–1845 (2006)
Blidia M., Chellali M., Haynes T.W., Henning M.A.: Independent and double domination in trees. Util. Math. 70, 159–173 (2006)
Blidia M., Chellali M., Volkmann L.: On the p-domination number of cactus graphs. Discuss. Math. Graph Theory 25, 355–361 (2005)
Blidia M., Chellali M., Volkmann L.: Some bounds on the p-domination number in trees. Discrete Math. 306, 2031–2037 (2006)
Blidia M., Chellali M., Volkmann L.: Bounds of the 2-domination number of graphs. Util. Math. 71, 209–216 (2006)
Brigham R.C., Dutton R.D.: Bounds on the domination number of a graph. Q. J. Math. Oxf. Ser. (2) 41, 269–275 (1990)
Caro Y.: On the k-domination and k-transveral numbers of graphs and hypergraphs. Ars Combin. 29C, 49–55 (1990)
Caro Y., Roditty Y.: A note on the k-domination number of a graph. Int. J. Math. Math. Sci. 13, 205–206 (1990)
Caro Y., Tuza Z.: Improved lower bounds on k-independence. J. Graph Theory 15, 99–107 (1991)
Caro Y., West D., Yuster R.: Connected domination and spanning trees with many leaves. SIAM J. Discrete Math. 13, 202–211 (2000) (electronic)
Caro Y., Yuster R.: Dominating a family of graphs with small connected subgraphs. Combin. Probab. Comput. 9, 309–313 (2000)
Chaluvaraju B., Chellali M., Vidya K.A.: Perfect k-domination in graphs. Australas. J. Combin. 48, 175–184 (2010)
Chambers, E.W., Kinnersley, B., Prince, N., West, D.B.: Extremal problems for Roman domination (2007, unpublished manuscript)
Chartrand G., Schuster S.: On the independence numbers of complementary graphs. Trans. New York Acad. Sci. Ser. II 36, 247–251 (1974)
Chellali M.: A note on the double domination number in trees. AKCE Int. J. Graphs Comb. 3, 147–150 (2006)
Chellali M.: Bounds on the 2-domination number in cactus graphs. Opuscula Math. 26, 5–12 (2006)
Chellali, M.: k-Domination stable graphs upon edge removal. Ars Combin. (in press)
Chellali M., Favaron O.: On k-star forming sets in graphs. J. Combin. Math. Combin. Comput. 68, 205–214 (2009)
Chellali M., Favaron O., Hansberg A., Volkmann L.: On the p-domination, the total domination and the connected domination numbers of graphs. J. Combin. Math. Combin. Comput. 73, 65–75 (2010)
Chellali M., Favaron O., Haynes T.W., Raber D.: Ratios of some domination parameters in trees. Discrete Math. 308, 3879–3887 (2008)
Chellali M., Haynes T.W.: On paired and double domination in graphs. Util. Math. 67, 161–171 (2005)
Chellali M., Haynes T.W.: A characterization of trees with unique minimum double dominating sets. Util. Math. 83, 233–242 (2010)
Chellali M., Haynes T.W., Volkmann L.: k-Independence stable graphs upon edge removal. Discuss. Math. Graph Theory 30, 265–274 (2010)
Chellali M., Khelladi A., Maffray F.: Exact double domination in graphs. Discuss. Math. Graph Theory 25, 291–302 (2005)
Chellali, M., Volkmann, L.: Characterization of trees with equal 2-domination number and domination number plus two. Discuss. Math. Graph Theory (in press)
Chen G., Jacobson M.S.: On a relationship between 2-dominating and 5-dominating sets in graphs. J. Combin. Math. Combin. Comput. 39, 139–145 (2001)
Chen X., Sun L.: Some new results on double domination in graphs. J. Math. Res. Expo. 25, 451–456 (2005)
Chen B., Zhou S.: Upper bounds for f-domination number of graphs. Discrete Math. 185, 239–243 (1998)
Cockayne E.J., Dreyer J.P.A., Hedetniemi S.M., Hedetniemi S.T.: Roman domination in graphs. Discrete Math. 278, 11–22 (2004)
Cockayne E.J., Favaron O., Payan C., Thomason A.G.: Contribution to the theory of domination, independence and irredundance in graphs. Discrete Math. 33, 249–258 (1981)
Cockayne E.J., Gamble B., Shepherd B.: An upper bound for the k-domination number of a graph. J. Graph Theory 9, 533–534 (1985)
Cockayne E.J., Grobler P.J.P., Gründlingh W.R., Munganga J., van Vuuren J.H.: Protection of a graph. Util. Math. 67, 19–32 (2005)
Cockayne E.J., Hedetniemi S.T.: Towards a theory of domination in graphs. Networks 7, 247–261 (1977)
Cockayne E.J., Thomason A.G.: An upper bound for the k-tuple domination number. J. Combin. Math. Combin. Comput. 64, 251–254 (2008)
Croitoru C., Suditu E.: Perfect stables in graphs. Inform. Process. Lett. 17, 53–56 (1983)
DeLaViña, E., Goddard, W., Henning, M.A., Pepper, R., Vaughan, E.R.: Bounds on the k-domination number of a graph. Appl. Math. Lett. (2011). doi:10.1016/j.aml.2011.01.013
Domke G.S., Hedetniemi S.T., Laskar R., Allan R.: Generalized packings and coverings of graphs. Congr. Numer. 62, 259–270 (1988)
Dorbec P., Gravier S., Klavžar S., Špacapan S.: Some results on total domination in direct products of graphs. Discuss. Math. Graph Theory 26, 103–112 (2006)
Duchet, P., Meyniel, H.: On Hadwiger’s number and the stability number, Graph theory (Cambridge, 1981), North-Holland Math. Stud., vol. 62, North-Holland, Amsterdam, 71–73 (1982)
Erfang S., Chuangyin D., Liying K.: A note on Nordhaus-Gaddum inequalities for domination. Discrete Appl. Math. 136, 83–85 (2004)
Fajtlowicz S.: On conjectures of Graffiti. III. Congr. Numer. 66, 23–32 (1988)
Favaron O.: On a conjecture of Fink and Jacobson concerning k-domination and k-dependence. J. Combin. Theory Ser. B 39, 101–102 (1985)
Favaron O.: k-domination and k-independence in graphs. Ars Combin. 25C, 159–167 (1988)
Favaron O.: An alternative definition of the k-irredundance. AKCE Int. J. Graphs Comb. 2, 33–38 (2005)
Favaron, O.: Bounds on the upper k-domination number and the upper k-star-forming number of a graph. J. Combin. Math. Combin. Comput. (in press)
Favaron, O.: Graduate course in the unversity of Blida (2005, unpublished)
Favaron O., Hansberg A., Volkmann L.: On k-domination and minimum degree in graphs. J. Graph Theory 57, 33–40 (2008)
Favaron O., Hartnell B.L.: On well-k-covered graphs. J. Combin. Math. Combin. Comput. 6, 199–205 (1989)
Favaron O., Hedetniemi S.M., Hedetniemi S.T., Rall D.F.: On k-dependent domination. Discrete Math. 249, 83–94 (2002)
Favaron O., Henning M.A., Puech J., Rautenbach D.: On domination and annihilation in graphs with claw-free blocks. Discrete Math. 231, 143–151 (2001)
Favaron, O., Kratsch, D.: Ratios of domination parameters. In: Advances in Graph Theory, pp. 173–182. Vishwa, Gulbarga (1991)
Favaron O., Mahéo M., Saclé J.F.: On the residue of a graph. J. Graph Theory 15, 39–64 (1991)
Fink, J.F., Jacobson, M.S.: n-domination in graphs. In: Graph Theory with Applications to Algorithms and Computer Science, pp. 283–300. Wiley, New York (1985)
Fink, J.F., Jacobson, M.S.: On n-domination, n-dependence and forbidden subgraphs. In: Graph Theory with Applications to Algorithms and Computer Science, pp. 301–311. Wiley, New York (1985)
Fink J.F., Jacobson M.S., Kinch L., Roberts J.: On graphs having domination number half their order. Period. Math. Hungar. 16, 287–293 (1985)
Fischermann M., Volkmann L.: A remark on a conjecture for the (k, p)-domination number. Util. Math. 67, 223–227 (2005)
Frucht R.W., Harary F.: On the corona of two graphs. Aequationes Math. 4, 322–325 (1970)
Fujisawa J., Hansberg A., Kubo T., Saito A., Sugita M., Volkmann L.: Independence and 2-domination in bipartite graphs. Australas. J. Combin. 40, 265–268 (2008)
Gagarin A., Zverovich V.E.: A generalised upper bound for the k-tuple domination number. Discrete Math. 308, 880–885 (2008)
Grigorescu E.: The insulation sequence of a graph. Discrete Appl. Math. 134, 77–90 (2004)
Gunther G., Hartnell B., Rall D.F.: Graphs whose vertex independence number is unaffected by single edge addition or deletion. Discrete Appl. Math. 46, 167–172 (1993)
Hansberg, A.: On the k-domination number, the domination number and the cycle of length four (submitted)
Hansberg A.: Bounds on the connected k-domination number. Discrete Appl. Math. 158(14), 1506–1510 (2010)
Hansberg A., Meierling D., Volkmann L.: A general method in the theory of domination in graphs. Int. J. Comput. Math. 87, 2915–2924 (2010)
Hansberg A., Meierling D., Volkmann L.: Independence and k-domination in graphs. Int. J. Comput. Math. 88, 905–915 (2011)
Hansberg, A. Pepper, R.: On k-domination and j-dependence in graphs (submitted)
Hansberg, A., Randerath, B., Volkmann, L.: Claw-free graphs with equal 2-domination and domination numbers (submitted)
Hansberg A., Volkmann L.: Characterization of block graphs with equal 2-domination number and domination number plus one. Discuss. Math. Graph Theory 27, 93–103 (2007)
Hansberg A., Volkmann L.: Characterization of unicyclic graphs with equal 2-domination number and domination number plus one. Util. Math. 77, 265–276 (2008)
Hansberg A., Volkmann L.: On graphs with equal domination and 2-domination numbers. Discrete Math. 308, 2277–2281 (2008)
Hansberg A., Volkmann L.: Lower bounds on the p-domination number in terms of cycles and matching number. J. Combin. Math. Combin. Comput. 68, 245–255 (2009)
Hansberg A., Volkmann L.: Upper bounds on the k-domination number and the k-Roman domination number. Discrete Appl. Math. 157, 1634–1639 (2009)
Hansberg, A., Volkmann, L.: On 2-domination and independence domination numbers of graphs. Ars Combin. (in press)
Harant J., Henning M.A.: On double domination in graphs. Discuss. Math. Graph Theory 25, 29–34 (2005)
Harant J., Henning M.A.: A realization algorithm for double domination in graphs. Util. Math. 76, 11–24 (2008)
Harary F., Haynes T.W.: Nordhaus-Gaddum inequalities for domination in graphs. Discrete Math. 155, 99–105 (1996)
Harary F., Haynes T.W.: The k-tuple domatic number of a graph. Math. Slovaca 48, 161–166 (1998)
Harary F., Haynes T.W.: Double domination in graphs. Ars Combin. 55, 201–213 (2000)
Haynes T.W., Hedetniemi S.T., Henning M.A., Slater P.J.: H-forming sets in graphs. Discrete Math. 262, 159–169 (2003)
Haynes T.W., Hedetniemi S.T., Slater P.J.: Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998)
Haynes T.W., Hedetniemi S.T., Slater P.J.: Domination in Graphs: Advanced Topics. Marcel Dekker, New York (1998)
Haynes T.W., Henning M.A.: Trees with two disjoint minimum independent dominating sets. Discrete Math. 304, 69–78 (2005)
Haynes T.W., Thacker D.: Double domination edge critical graphs. Util. Math. 78, 139–149 (2009)
Hedetniemi, S.M., Hedetniemi, S.T., Laskar, R.: Domination in trees: models and algorithms. In: Graph Theory with Applications to Algorithms and Computer Science, pp. 423–442. Wiley, New York (1985)
Henning M.A.: Graphs with large double domination numbers. Discuss. Math. Graph Theory 25, 13–28 (2005)
Henning M.A., Oellermann O.R., Swart H.C.: Bounds on distance domination parameters. J. Combin. Inform. Syst. Sci. 160, 11–18 (1991)
Hopkins G., Staton W.: Vertex partition and k-small subsets of graphs. Ars Combin. 22, 19–24 (1986)
Ionascu, E.J., Pritikin, D., Wright, S.E.: k-dependence and domination in Kings graphs (2006, preprint). arXiv:math0608140v1
Jacobson M.S., Peters K.: Complexity questions for n-domination and related parameters. Congr. Numer. 68, 7–22 (1989)
Jacobson M.S., Peters K., Rall D.F.: On n-irredundance and n-domination. Ars Combin. 29B, 151–160 (1990)
Jaeger F., Payan C.: Relations du type Nordhaus-Gaddum pour le nombre d’arbsoption d’un graphs simple. C. R. Acad. Sci. Paris 274, 728–730 (1972)
Jagota A., Narasimhan G., Šoltés L.: A generalization of maximal independent sets. Discrete Appl. Math. 109, 223–235 (2001)
Jelen F.: k-Independence and the k-residue of a graph. J. Graph Theory 32, 241–249 (1999)
Kala R., Nirmala Vasantha T.R.: Restrained double domination number of a graph. AKCE Int. J. Graphs Comb. 5, 73–82 (2008)
Kämmerling K., Volkmann L.: The k-domatic number of a graph. Czechoslov. Math. J. 59, 539–550 (2009)
Kämmerling K., Volkmann L.: Roman k-domination in graphs. J. Korean Math. Soc. 46, 1309–1318 (2009)
Karami H., Khodkar A., Sheikholeslami S.M.: Trees whose double domination number is twice their domination number. Congr. Numer. 186, 49–56 (2007)
Khodkar A., Sheikholeslami S.M., Hasanzadeh H.: Bounds on double domination numbers of graphs. Congr. Numer. 177, 77–87 (2005)
Khodkar A., Sheikholeslami S.M.: On perfect double dominating sets in grids, cylinders and tori. Australas. J. Combin. 37, 131–139 (2007)
Klasing R., Laforest C.: Hardness results and approximation algorithms of k-tuple domination in graphs. Inform. Process. Lett. 89, 75–83 (2004)
Korneffel T., Meierling D., Volkmann L.: A remark on the (2,2)-domination number. Discuss. Math. Graph Theory 28, 361–366 (2008)
Kulli, V.: On n-total domination number in graphs. Graph theory, combinatorics, algorithms, and applications, pp. 319–324. SIAM, Philadelphia (1991)
Liao C.-S., Chang G.J.: k-tuple domination in graphs. Inform. Process. Lett. 87, 45–50 (2003)
Lovász L.: On the ratio of optimal and integral fractional covers. Discrete Math. 13, 383–390 (1975)
Lu Y., Hou X., Xu J.: A note on the p-domination number of trees. Opuscula Math. 29, 157–164 (2009)
Lu Y., Hou X., Xu J.: On the (2, 2)-domination number of trees. Discuss. Math. Graph Theory 30, 185–199 (2010)
Lu, Y., Hou, X., Xu, J., Li, N.: Trees with unique minimum p-dominating sets. Util. Math. (in press)
Lu Y., Hou X., Xu J., Li N.: A characterization of (γ t , γ 2)-trees. Discuss. Math. Graph Theory 30, 425–435 (2010)
Maddox R.B.: On k-dependent subsets and partitions of k-degenerate graphs. Congr. Numer. 66, 11–14 (1988)
Mehri J., Mirnia M., Sheikholeslami S.M.: 3-tuple domination number in complete grid graphs. Int. Math. Forum 21-24, 1099–1112 (2006)
Meir A., Moon J.W.: Relations between packing and covering number of a tree. Pacific J. Math. 61, 225–233 (1975)
Ore, O.: Theory of Graphs. In: Amer. Math. Soc. Colloq. Publ. vol. 38. Amer. Math. Soc., Providence (1962)
Payan C.: Sur le nombre d’absorption d’un graphe simple. Cahiers Centre Études Recherche Opér. 17, 307–317 (1975)
Payan C., Xuong N.H.: Domination-balanced graphs. J. Graph Theory 6, 23–32 (1982)
Pepper, R.: Implications of some observations about the k-domination number (in press)
Prince, N.: Nordhaus-Gaddum bounds for k-domination in graphs (in press)
Randerath B., Volkmann L.: Characterization of graphs with equal domination and covering number. Discrete Math. 191, 159–169 (1998)
Rautenbach D., Volkmann L.: New bounds on the k-domination number and the k-tuple domination number. Appl. Math. Lett. 20, 98–102 (2007)
ReVelle C.S., Rosing K.E.: Defendens imperium romanum: a classical problem in military strategy. Am. Math. Mon. 107, 585–594 (2000)
Shaheen, R.S.: Bounds for the 2-domination number of toroidal grid graphs. In: First Conference on Mathematical Sciences, pp. 359–363. Zarqu Priv. Univ., Zarka (2006)
Sheikholeslami S.M., Volkmann L.: The Roman domatic number of a graph. Appl. Math. Lett. 23, 1295–1300 (2010)
Sheikholeslami, S.M., Volkmann, L.: The Roman k-domatic number of a graph. Acta Math. Sin. (Engl. Ser.). (in press)
Steward I.: Defend the Roman Empire!. Sci. Am. 281, 136–139 (1999)
Stracke C., Volkmann L.: A new domination conception. J. Graph Theory 17, 315–323 (1993)
Topp, J.: Domination, independence and irredundance in graphs. Dissertationes Math. (Rozprawy Mat.) 342 (1995)
Volkmann L.: Graphen und Digraphen: Eine Einführung in die Graphentheorie, vol. XIII. Springer, Wien (1991)
Volkmann L.: On perfect and unique maximum independent sets in graphs. Math. Bohemica 129, 273–282 (2004)
Volkmann, L.: Graphen an allen Ecken und Kanten, vol. XVI. RWTH Aaachen (2006). http://www.math2.rwth-aachen.de/files/gt/buch/graphen_an_allen_ecken_und_kanten.pdf
Volkmann L.: Some remarks on lower bounds on the p-domination number in trees. J. Combin. Math. Combin. Comput. 61, 159–167 (2007)
Volkmann L.: A Nordhaus-Gaddum-type result for the 2-domination number. J. Combin. Math. Combin. Comput. 64, 227–235 (2008)
Volkmann L.: Connected p-domination in graphs. Util. Math. 79, 81–90 (2009)
Volkmann L.: A bound on the k-domination number of a graph. Czechoslov. Math. J. 60, 77–83 (2010)
Volkmann, L.: Bounds on the k-tuple domatic number of a graph. Math. Slovaca (in press)
Wang B., Xiang K.N.: On k-tuple domination of random graphs. Appl. Math. Lett. 22, 1513–1517 (2009)
Wei, V.K.: A lower bound on the stablity number of a simple graph. Bell Laboratories Technical Memorandum 81-11217-9, Murray Hill (1981)
Wieland B., Godbole A.P.: On the domination number of a random graph. Electron J. Combin. 8, R37 (2001)
Xu G., Kang L., Shan E., Yan H.: Proof of a conjecture on k-tuple domination in graphs. Appl. Math. Lett. 21, 287–290 (2008)
Zelinka B.: On k-domatic numbers of graphs. Czechoslov. Math. J. 33, 309–313 (1983)
Zelinka B.: On k-ply domatic numbers of graphs. Math. Slovaka 34, 313–318 (1984)
Zelinka, B.: Domatic numbers of graphs and their variants: a survey. In [95], pp 351–374 (1998)
Zhou S.: On f-domination number of a graph. Czechoslov. Math. J. 46(121), 489–499 (1996)
Zhou S.: Inequalities involving independence domination, f-domination, connected and total f-domination numbers. Czechoslov. Math. J. 50(125), 321–330 (2000)
Zverovich V.: The k-tuple domination number revisited. Appl. Math. Lett. 21, 1005–1011 (2008)
Author information
Authors and Affiliations
Corresponding author
Additional information
M. Chellali was supported by “Programmes Nationaux de Recherche: Code 8/u09/510”.
A. Hansberg was partially supported by the Ministry of Science and Innovation, Spain, and the European Regional Development Fund (ERDF) under project MTM2008-066200-C03-02/MTM.
Rights and permissions
About this article
Cite this article
Chellali, M., Favaron, O., Hansberg, A. et al. k-Domination and k-Independence in Graphs: A Survey. Graphs and Combinatorics 28, 1–55 (2012). https://doi.org/10.1007/s00373-011-1040-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-011-1040-3
Keywords
- k-Domination
- k-Independence
- k-Tuple domination
- k-Irredundance
- k-Star-forming
- l-Total k-domination
- Connected k-domination