تعداد نشریات | 11 |
تعداد شمارهها | 210 |
تعداد مقالات | 2,101 |
تعداد مشاهده مقاله | 2,883,259 |
تعداد دریافت فایل اصل مقاله | 2,090,491 |
On the Roman domination number of the subdivision of some graphs | ||
Journal of Discrete Mathematics and Its Applications | ||
دوره 9، شماره 4، اسفند 2024، صفحه 321-333 اصل مقاله (295.77 K) | ||
نوع مقاله: Full Length Article | ||
شناسه دیجیتال (DOI): 10.22061/jdma.2024.11309.1099 | ||
نویسندگان | ||
Rostam Yarke Salkhori* ؛ Ebrahim Vatandoost؛ Ali Behtoei | ||
Imam Khomeini International University | ||
تاریخ دریافت: 05 آبان 1403، تاریخ بازنگری: 30 آبان 1403، تاریخ پذیرش: 11 آذر 1403 | ||
چکیده | ||
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 . | ||
کلیدواژهها | ||
Roman dominating function؛ bipartite graph؛ tree | ||
مراجع | ||
[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 | ||
آمار تعداد مشاهده مقاله: 24 تعداد دریافت فایل اصل مقاله: 60 |