On the Roman domination number of the subdivision of some graphs

Document Type : Full Length Article

Authors

Imam Khomeini International University

Abstract

A Roman dominating function on a graph G = (V, E) is a function
f : V(G) → {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of a Roman dominating function is the value f(V) = ∑u∈V(G)f(u).
The minimum possible weight of a Roman dominating function on G is called the Roman domination number of G and is denoted by γR(G). In this paper, and among some other results, we provide some bounds for the Roman domination number of the subdivision graph S(G) of an arbitrary graph G.
Also, we determine the exact value of γR(S(G)) when G is Kn, Kr,s or Kn1,n2,...,nk
.

Graphical Abstract

On the Roman domination number of the subdivision of some graphs

Keywords

Main Subjects

References

[1] S. Ahmadi, E. Vatandoost, A. Behtoei, Domination number and identifying
code number of the subdivision graphs, J. Algebra. Syst. Articles in Press.
https://doi.org/10.22044/jas.2023.12257.1649
[2] W. Barrett, S. Butler, M. Catral, S. M. Fallat, H. T. Hallk, L. Hogben, M. Young, The maximum
nullity of a complete subdivision graph is equal to its zero forcing number, Electron. J. Linear
Algebra 27 (2014) 444–457. https://doi.org/10.13001/1081-3810.1629
[3] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, L. Volkmann, Roman domination in graphs, In:
Topics in Domination in Graphs, Eds. T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Springer
2020 365–409.https://doi.org/10.1007/978-3-030-51117-3 11
[4] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, L. Volkmann, Varieties of Roman domination,
In: Structures of Domination in Graphs, Eds. T.W. Haynes, S.T. Hedetniemi and M.A. Henning,
Springer 2021, 273-307. https://doi.org/10.1007/978-3-030-58892-2 10
[5] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, L. Volkmann, Varieties of Roman domination II,
AKCE Int. J. Graphs Comb. 17 (2020) 966–984.https://doi.org/10.1016/j.akcej.2019.12.001
[6] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, L. Volkmann, The Roman domatic problem in graphs and digraphs: A survey, Discuss. Math. Graph Theory 42 (2022) 861–891.
https://doi.org/10.7151/dmgt.2313
[7] E. J. Cockayne, P. M. Dreyer, S. M. Hedetniemi, S. T. Hedetniemi, Roman domination in graphs,
Discrete Math. 278 (2004) 11–22.https://doi.org/10.1016/j.disc.2003.06.004
[8] S. M. Mirafzal, Some algebraic properties of the subdivision graph of a graph, Commun. Comb.
Optim. 9 (2024) 297–307. https://doi.org/10.22049/cco.2023.28270.1494
[9] R. Y. Salkhori, E. Vatandoost, A. Behtoei, 2-Rainbow domination number of the subdivision of
graphs, Commun. Comb. Optim. Articles in Press https://doi.org/10.22049/cco.2024.28850.1749
[10] Y. Wu, N. J. Rad, Bounds on the 2−rainbow domination of graph, Graphs Combin. 29 (2013) 25–33.
https://doi.org/10.1007/s00373-012-1158-y
[11] T. Zec, On the Roman domination problem of some Johnson graphs, Filomat 37 (2023) 2067–2075.
https://doi.org/10.2298/fil2307067z
Journal of Discrete Mathematics and Its Applications
Volume 9, Issue 4
December 2024
Pages 321-333

Files

History

  • Receive Date: 26 October 2024
  • Revise Date: 20 November 2024
  • Accept Date: 01 December 2024
  • Publish Date: 01 December 2024

Share

How to cite

Statistics