[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

On the Roman domination subdivision number of a graph

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

Abstract

A Roman dominating function (RDF) of a graph G is a labeling \(f:V(G)\longrightarrow \{0,1,2\}\) such that every vertex with label 0 has a neighbor with label 2. The weight of an RDF is the sum of its functions values over all vertices, and the Roman domination number of G is the minimum weight of an RDF of G. The Roman domination subdivision number \(\mathrm {sd}_{\gamma _{R}}(G)\) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the Roman domination number of G. In this paper, we present a new upper bound on the Roman domination subdivision number by showing that for every connected graph G of order at least three,

$$\begin{aligned} \mathrm {sd}_{\gamma _{R}}(G)\le 3+\min \{\deg _2(v)\mid v\in V\;\mathrm {and} \;d(v)\ge 2\}, \end{aligned}$$

where \(\deg _2(v)\) is the number of vertices of G at distance 2 from vertex v. Moreover, we show that the decision problem associated with \(\mathrm {sd}_{\gamma _{R}}(G)\) is NP-hard for bipartite graphs.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  • Aram A, Sheikholeslami SM, Favaron O (2009) Domination subdivision numbers of trees. Discrete Math 309:622–628

    Article  MathSciNet  Google Scholar 

  • Atapour M, Khodkar A, Sheikholeslami SM (2009) Roman domination subdivision number of a graph. Aequ Math 78:237–245

    Article  MathSciNet  Google Scholar 

  • Bahremandpour A, Hu F-T, Sheikholeslami SM (2013) On the Roman bondage number of a graph. Discrete Math Algorithms Appl 5:Article ID: 1350001

  • Chellali M, Jafari Rad N, Sheikholeslami SM, Volkmann L (2020a) Roman domination in graphs. In: Haynes TW, Hedetniemi ST, Henning MA (eds) Topics in domination in graphs. Springer (to appear)

  • Chellali M, Jafari Rad N, Sheikholeslami SM, Volkmann L (2020b) Varieties of Roman domination. In: Haynes TW, Hedetniemi ST, Henning MA (eds) Structures of domination in graphs. Springer (to appear)

  • Chellali M, Jafari Rad N, Sheikholeslami SM, Volkmann L (2020c) Varieties of Roman domination II. AKCE J Graphs Combin (to appear)

  • Chellali M, Jafari Rad N, Sheikholeslami SM, Volkmann L (2020d) A survey on Roman domination parameters in directed graphs. J Combin Math Combin Comput (to appear)

  • Chellali M, Jafari Rad N, Sheikholeslami SM, Volkmann L (2020e) The Roman domatic problem in graphs and digraphs: a survey. Discuss Math Graph Theory. https://doi.org/10.7151/dmgt.2313

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

    Article  MathSciNet  Google Scholar 

  • Dehgardi N, Sheikholeslami SM, Volkmann L (2015) The rainbow domination subdivision numbers of graphs. Mat Vesnik 67:102–114

    MathSciNet  MATH  Google Scholar 

  • Favaron O, Karami H, Sheikholeslami SM (2008a) Disprove of a conjecture the domination subdivision number of a graph. Graphs Combin 24:309–312

    Article  MathSciNet  Google Scholar 

  • Favaron O, Karami H, Sheikholeslami SM (2008b) Connected domination subdivision numbers of graphs. Util Math 77:101–111

    MathSciNet  MATH  Google Scholar 

  • Haynes TW, Hedetniemi ST, van der Merwe LC (2003) Total domination subdivision numbers. JCMCC 44:115–128

    MathSciNet  MATH  Google Scholar 

  • Khodkar A, Mobaraky BP, Sheikholeslami SM (2008) Upper bounds for the Roman domination subdivision number of a graph. AKCE J Graphs Combin 5:7–14

    MathSciNet  MATH  Google Scholar 

  • Khodkar A, Mobaraky BP, Sheikholeslami SM (2013) Roman dominatiom subdivision number of a graph and its complement. Ars Combin 111:97–100

    MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  • Velammal S (1997) Studies in graph theory: covering, independence, domination and related topics, Ph.D. Thesis (Manonmaniam Sundaranar University, Tirunelveli)

Download references

Acknowledgements

This work was supported by the National Key R & D Program of China (Grant No. 2019YFA0706402) and the Natural Science Foundation of Guangdong Province under grant 2018A0303130115.

Author information

Authors and Affiliations

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

    J. Amjadi & R. Khoeilar

  2. LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria

    M. Chellali

  3. Institute of Computing Science and Technology, Guangzhou University, Guangzhou, 510006, China

    Z. Shao

Authors
  1. J. Amjadi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. R. Khoeilar
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. M. Chellali
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Z. Shao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to J. Amjadi.

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

Amjadi, J., Khoeilar, R., Chellali, M. et al. On the Roman domination subdivision number of a graph. J Comb Optim 40, 501–511 (2020). https://doi.org/10.1007/s10878-020-00597-x

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-020-00597-x

Keywords

Mathematics Subject Classification

Search

Navigation