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

An upper bound on the double Roman domination number

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

Abstract

A double Roman dominating function (DRDF) on a graph \(G=(V,E)\) is a function \(f : V \rightarrow \{0, 1, 2, 3\}\) having the property that if \(f(v) = 0\), then vertex v must have at least two neighbors assigned 2 under f or one neighbor w with \(f(w)=3\), and if \(f(v)=1\), then vertex v must have at least one neighbor w with \(f(w)\ge 2\). The weight of a DRDF f is the value \(f(V) = \sum _{u \in V}f(u)\). The double Roman domination number \(\gamma _{dR}(G)\) of a graph G is the minimum weight of a DRDF on G. Beeler et al. (Discrete Appl Math 211:23–29, 2016) observed that every connected graph G having minimum degree at least two satisfies the inequality \(\gamma _{dR}(G)\le \frac{6n}{5}\) and posed the question whether this bound can be improved. In this paper, we settle the question and prove that for any connected graph G of order n with minimum degree at least two, \(\gamma _{dR}(G)\le \frac{8n}{7}\).

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

Fig. 1

Similar content being viewed by others

References

  • Abdollahzadeh Ahangar H, Amjadi J, Atapour M, Chellali M, Sheikholeslami SM (2017a) Double Roman on trees. Ars Combin (in press)

  • Abdollahzadeh Ahangar H, Amjadi J, Chellali M, Nazari-Moghaddam S, Sheikholeslami SM (2018) Trees with double Roman domination number twice the domination number plus two. Iran J Sci Technol Trans A Sci. https://doi.org/10.1007/s40995-018-0535-7

  • Abdollahzadeh Ahangar H, Chellali M, Sheikholeslami SM (2017b) On the double Roman domination in graphs. Discrete Appl Math 232:1–7

    Article  MathSciNet  MATH  Google Scholar 

  • Beeler RA, Haynes TW, Hedetniemi ST (2016) Double Roman domination. Discrete Appl Math 211:23–29

    Article  MathSciNet  MATH  Google Scholar 

  • Cockayne EJ, Dreyer PA Jr, Hedetniemic SM, Hedetniemic ST (2004) Roman domination in graphs. Discrete Math 278:11–22

    Article  MathSciNet  Google Scholar 

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

    MATH  Google Scholar 

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

    MATH  Google Scholar 

  • Henning MA, Hedetniemi ST (2003) Defending the Roman Empire-a new strategy. Discrete Math 266:239–251

    Article  MathSciNet  MATH  Google Scholar 

  • Jafari Rad N, Rahbani H (2018) Some progress on the double Roman domination in graphs. Discuss Math Graph Theory (to appear)

  • McCuaig W, Shepherd B (1989) Domination in graphs with minimum degree two. J Graph Theory 13(6):749–762

    Article  MathSciNet  MATH  Google Scholar 

  • ReVelle CS (1997) Can you protect the Roman Empire? Johns Hopkins Mag 49:40–43

    Google Scholar 

  • Revelle CS, Rosing KE (2000) Defendens imperium romanum: a classical problem in military strategy. Am Math Monthly 107(7):585–594

    Article  MathSciNet  MATH  Google Scholar 

  • Stewart I (1999) Defend the Roman Empire. Sci Am 281:136–139

    Article  Google Scholar 

  • Volkmann L (2018a) The double Roman domatic number of a graph. J Comb Math Comb Comput 104:205–215

    MathSciNet  MATH  Google Scholar 

  • Volkmann L (2018b) Double Roman domination and domatic numbers of graphs. Commun Comb Optim 3:71–77

    MathSciNet  MATH  Google Scholar 

  • Zhang X, Li Z, Jiang H, Shao Z (2018) Double Roman domination in trees. Inf Process Lett 134:31–34

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, Islamic Republic of Iran

    J. Amjadi, S. Nazari-Moghaddam & S. M. Sheikholeslami

  2. Lehrstuhl II für Mathematik, RWTH Aachen University, 52056, Aachen, Germany

    L. Volkmann

Authors
  1. J. Amjadi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S. Nazari-Moghaddam
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. S. M. Sheikholeslami
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. L. Volkmann
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to S. M. Sheikholeslami.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Amjadi, J., Nazari-Moghaddam, S., Sheikholeslami, S.M. et al. An upper bound on the double Roman domination number. J Comb Optim 36, 81–89 (2018). https://doi.org/10.1007/s10878-018-0286-6

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-018-0286-6

Keywords

Search

Navigation