Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On the k-domination number of digraphs

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

Let \(k\ge 1\) be an integer and let D be a digraph with vertex set V(D). A subset \(S\subseteq V(D)\) is called a k-dominating set if every vertex not in S has at least k predecessors in S. The k-domination number \(\gamma _{k}(D)\) of D is the minimum cardinality of a k-dominating set in D. We know that for any digraph D of order n, \(\gamma _{k}(D)\le n\). Obviously the upper bound n is sharp for a digraph with maximum in-degree at most \(k-1\). In this paper we present some lower and upper bounds on \(\gamma _{k}(D)\). Also, we characterize digraphs achieving these bounds. The special case \(k=1\) mostly leads to well known classical results.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Bang J, Gutin G (2008) Digraphs theory, algorithms and applications. Springer, Berlin

    MATH  Google Scholar 

  • Berge C (1962) The theory of graphs and its applications. Wiley, New York

    MATH  Google Scholar 

  • Caro Y (1980) Communicated by N. Linial (unpublished)

  • Chellali M, Favaron O, Hansberg A, Volkmann L (2012) \(k\)-domination and \(k\)-independence in graphs: a survey. Graphs Combin 281:1–55

    Article  MathSciNet  MATH  Google Scholar 

  • Cockayne EJ, Gamble B, Shepherd B (1985) An upper bound for the \(k\)-domination number of a graph. J Graph Theory 9:533–534

    Article  MathSciNet  MATH  Google Scholar 

  • Fink JF, Jacobson MS (1985a) n-domination in graphs. Graph theory with applications to algorithms and computer science. Wiley, New York, pp 283–300

    Google Scholar 

  • Fink JF, Jacobson MS (1985b) On n-domination, n-dependence and forbidden subgraphs. In: Graph theory with applications to algorithms and computer science. Wiley, New York, pp 301–311

  • Fraenkel A (1981) Planar kernel and grundy with \(d\le 3\), \(dout\le 2\), \(din\le 2\) are NP-complete. Discrete Appl Math 3:257–262

    Article  MathSciNet  Google Scholar 

  • Garey MR, Johnson DS (1979) Computers and intractability. A guide to the theory of NP-completeness. Freeman, San Francisco

    MATH  Google Scholar 

  • Ghoshal J, Laskar R, Pillone D (1998) Topics on domination in directed graphs. In: Haynes TW, Hedetniemi ST, Slater PJ (eds) Domination in graphs: advanced topics. Marcel Dekker, New York, pp 401–437

    Google Scholar 

  • Haynes TW, Hedetniemi ST, Slater PJ (1998a) Fundamentals of domination in graphs. Marcel Dekker, New York

    MATH  Google Scholar 

  • Haynes TW, Hedetniemi ST, Slater PJ (1998b) Domination in graphs: advanced topics. Marcel Dekker, New York

    MATH  Google Scholar 

  • Jacobson MS, Peters K (1989) Complexity questions for n-domination and related parameters. Congr Numer 68:7–22

    MathSciNet  Google Scholar 

  • Lee C (1994) On the domination number of a digraph. Ph.D. Dissertation, Michigan State University

  • Lee C (1998) Domination in digraphs. J Korean Math Soc 35(4):843–853

    MathSciNet  MATH  Google Scholar 

  • Ore O (1962) Theory of graphs, vol XXXVIII. American Mathematical Society Colloquium Publications, Providence

    MATH  Google Scholar 

  • Ramoul A, Blidia M (2017) A new generalization of kernels in digraphs. Discrete Appl Math 217:673–684

    Article  MathSciNet  MATH  Google Scholar 

  • Wei VK (1981) A lower bound on the stability number of a simple graph. Bell Laboratories Technical, Memorandum, 81–11217-9. Murray Hill, NJ

Download references

Author information

Authors and Affiliations

  1. Lamda-RO, Department of Mathematics, University of Blida 1, B.P. 270, Blida, Algeria

    Lyes Ouldrabah & Mostafa Blidia

  2. Department of Mathematics, University of Médéa, Medea, Algeria

    Ahmed Bouchou

Authors
  1. Lyes Ouldrabah
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mostafa Blidia
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ahmed Bouchou
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lyes Ouldrabah.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ouldrabah, L., Blidia, M. & Bouchou, A. On the k-domination number of digraphs. J Comb Optim 38, 680–688 (2019). https://doi.org/10.1007/s10878-019-00405-1

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-019-00405-1

Keywords

Mathematics Subject Classification

Search

Navigation