On the Roman domination number of the subdivision of some graphs

Document Type : Full Length Article

Authors

Imam Khomeini International University, P.O. Box 34148- 96818, Qazvin, I. R. Iran

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) = \sum_{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 $\gamma_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 $\gamma_R(S(G))$ when $G$ is $K_n$, $K_{r,s} or $K_{n_1,n_2,...,n_k}$.

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
  • First Publish Date: 01 December 2024
  • Publish Date: 01 December 2024

Share

How to cite

Statistics