DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

M. Chellali

Mustapha Chellali

Department of MathematicsUniversity of BlidaB.P. 270, Blida, ALGERIA

email: m_chellali@yahoo.com

0000-0001-5231-6195

N. Jafari Rad

Nader Jafari Rad

Department of Mathematics Shahrood Niversity of TechnologyUniversity Blvd. Shahrood IRAN

email: n.jafarirad@gmail.com

S.M. Sheikholeslami

Seyed Mahmoud Sheikholeslami

Azarbaijan Shahid Madani university

email: s.m.sheikholeslami@azaruniv.ac.ir

L. Volkmann

Lutz Volkmann

Lehrstuhl II für Mathematik, RWTH-Aachen52056 Aachen GERMANY

email: volkm@math2.rwth-aachen.de

0000-0003-3496-277X

Title:

The Roman domatic problem in graphs and digraphs: a survey

PDF

Source:

Discussiones Mathematicae Graph Theory 42(3) (2022) 861-891

Received: 2019-09-26 , Revised: 2020-02-21 , Accepted: 2020-02-24 , Available online: 2020-03-14 , https://doi.org/10.7151/dmgt.2313

Abstract:

In this paper, we survey results on the Roman domatic number and its variants in both graphs and digraphs. This fifth survey completes our works on Roman domination and its variations published in two book chapters and two other surveys.

Keywords:

Roman domination, domatic

References:

  1. H.A. Ahangar, M.A. Henning, C. Löwenstein, Y. Zhao and V. Samodivkin, Signed Roman domination in graphs, J. Comb. Optim. 27 (2014) 241–255.
    https://doi.org/10.1007/s10878-012-9500-0
  2. H.A. Ahangar, M.A. Henning, V. Samodivkin and I.G. Yero, Total Roman domination in graphs, Appl. Anal. Discrete Math. 10 (2016) 501–517.
    https://doi.org/10.2298/AADM160802017A
  3. J. Amjadi, The signed total Roman domatic number of a digraph, Discrete Math. Algorithms Appl. 10 (2018) 1850020.
    https://doi.org/10.1142/S1793830918500209
  4. J. Amjadi, Twin signed total Roman domatic numbers in digraphs, Commun. Comb. Optim. 6 (2021) 17–26.
    https://doi.org/10.22049/CCO.2020.26791.1142
  5. J. Amjadi, S. Nazari-Moghaddam and S.M. Sheikholeslami, Total Roman domatic number of a graph, Asian-Eur. J. Math. 13 (2020) 2050110.
    https://doi.org/10.1142/S1793557120501107
  6. J. Amjadi and M. Soroudi, Twin signed total Roman domination numbers in digraphs, Asian-Eur. J. Math. 11 (2018) 1850034.
    https://doi.org/10.1142/S1793557118500341
  7. H. Aram, S. Norouzian, S.M. Sheikholeslami and L. Volkmann, The distance Roman domination numbers of graphs, Discuss. Math. Graph Theory 33 (2013) 717–730.
    https://doi.org/10.7151/dmgt.1703
  8. H. Aram, S.M. Sheikholeslami and L. Volkmann, The distance Roman domatic number of a graph, AKCE Int. J. Graphs Comb. 9 (2012) 205–212.
  9. R.A. Beeler, T.W. Haynes and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016) 23–29.
    https://doi.org/10.1016/j.dam.2016.03.017
  10. A. Bodaghli, S.M. Sheikholeslami and L. Volkmann, Twin signed Roman domination numbers in directed graphs, Tamkang J. Math. 47 (2016) 357–371.
    https://doi.org/10.5556/j.tkjm.47.2016.2035
  11. E.J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11–22.
    https://doi.org/10.1016/j.disc.2003.06.004
  12. M. Chellali, T.W. Haynes, S.T. Hedetniemi and A.A. McRae, Roman $\{2\}$-domination, Discrete Appl. Math. 204 (2016) 22–28.
    https://doi.org/10.1016/j.dam.2015.11.013
  13. M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, Roman domination in graphs, in: Topics in Domination in Graphs, T.W. Haynes, S.T. Hedetniemi and M.A. Henning (Ed(s)), (Springer 2020) 365–409.
    https://doi.org/10.1007/978-3-030-51117-3_11
  14. M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, Varieties of Roman domination, in: Structures of Domination in Graphs, T.W. Haynes, S.T. Hedetniemi and M.A. Henning (Ed(s)), (Springer 2021).
  15. M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and 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
  16. M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, A survey on Roman domination parameters in directed graphs, J. Combin. Math. Combin. Comput. 115 (2020) 141–171.
  17. E.J. Cockayne, P.J.P. Grobler, W.R. Gründlingh, J. Munganga and J.H. van Vuuren, Protection of a graph, Util. Math. 67 (2005) 19–32.
  18. E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977) 247–261.
    https://doi.org/10.1002/net.3230070305
  19. G. Hao, X. Chen and L. Volkmann, Double Roman domination in digraphs, Bull. Malays. Math. Sci. Soc. 42 (2019) 1907–1920.
    https://doi.org/10.1007/s40840-017-0582-9
  20. G. Hao, Z. Xie and X. Chen, A note on Roman domination of digraphs, Discuss. Math. Graph Theory 39 (2019) 13–21.
    https://doi.org/10.7151/dmgt.2067
  21. T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).
  22. T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, Inc., New York, 1998).
  23. M.A. Henning and L. Volkmann, Signed Roman $k$-domination in graphs, Graphs Combin. 32 (2016) 175–190.
    https://doi.org/10.1007/s00373-015-1536-3
  24. K. Kämmerling and L. Volkmann, The Roman $k$-domination in graphs, J. Korean Math. Soc. 46 (2009) 1309–1318.
    https://doi.org/10.4134/JKMS.2009.46.6.1309
  25. M. Kamaraj and P. Jakkamal, Directed Roman domination in digraphs, Int. J. Comb. Graph Theory Appl. 4 (2011) 103–116.
  26. C.-H. Liu and G.J. Chang, Roman domination on strongly chordal graphs, J. Comb. Optim. 26 (2013) 608–619.
    https://doi.org/10.1007/s10878-012-9482-y
  27. A.P. Kazemi, S.M. Sheikholeslami and L. Volkmann, The Roman $(k,k)$-domatic number of a graph, Ann. Math. Inform. 38 (2011) 45–57.
  28. C.S. ReVelle and K.E. Rosing, Defendens Iperium Romanum: A classical problem in military strategy, Amer. Math. Monthly 107 (2000) 585–594.
    https://doi.org/10.1080/00029890.2000.12005243
  29. S.M. Sheikholeslami and L. Volkmann, The Roman domatic number of a graph, Appl. Math. Lett. 23 (2010) 1295–1300.
    https://doi.org/10.1016/j.aml.2010.06.016
  30. S.M. Sheikholeslami and L. Volkmann, The Roman $k$-domatic number of a graph, Acta Math. Sin. (Engl. Ser.) 27 (2011) 1899–1906.
    https://doi.org/10.1007/s10114-011-0385-0
  31. S.M. Sheikholeslami and L. Volkmann, The Roman domination number of a digraph, Acta Univ. Apulensis Math. Inform. 27 (2011) 77–86.
  32. S.M. Sheikholeslami and L. Volkmann, The signed Roman domatic number of a graph, Ann. Math. Inform. 40 (2012) 105–112.
  33. S.M. Sheikholeslami and L. Volkmann, Signed Roman domination in digraphs, J. Comb. Optim. 30 (2015) 456–467.
    https://doi.org/10.1007/s10878-013-9648-2
  34. S.M. Sheikholeslami and L. Volkmann, The signed Roman domatic number of a digraph, Electron. J. Graph Theory Appl. 3 (2015) 85–93.
    https://doi.org/10.5614/ejgta.2015.3.1.9
  35. S.M. Sheikholeslami and L. Volkmann, Twin signed Roman domatic numbers in digraphs, Tamkang J. Math. 48 (2017) 265–272.
    https://doi.org/10.5556/j.tkjm.48.2017.2306
  36. P.J. Slater and E.L. Trees, Multi-fractional domination, J. Combin. Math. Combin. Comput. 40 (2002) 171–181.
  37. I. Stewart, Defend the Roman Empire, Sci. Amer. 281 (1999) 136–139.
    https://doi.org/10.1038/scientificamerican1299-136
  38. H. Tan, H. Liang, R. Wang and J. Zhou, Computing Roman domatic number of graphs, Inform. Process. Lett. 116 (2016) 554–559.
    https://doi.org/10.1016/j.ipl.2016.04.010
  39. L. Volkmann, The signed Roman $k$-domatic number of a graph, Discrete Appl. Math. 180 (2015) 150–157.
    https://doi.org/10.1016/j.dam.2014.07.030
  40. L. Volkmann, Signed total Roman domination in graphs, J. Comb. Optim. 32 (2016) 855–871.
    https://doi.org/10.1007/s10878-015-9906-6
  41. L. Volkmann, On the signed total Roman domination and domatic numbers of graphs, Discrete Appl. Math. 214 (2016) 179–186.
    https://doi.org/10.1016/j.dam.2016.06.006
  42. L. Volkmann, Signed Roman $k$-domination in digraphs, Graphs Combin. 32 (2016) 1217–1227.
    https://doi.org/10.1007/s00373-015-1641-3
  43. L. Volkmann, The signed Roman $k$-domatic number of digraphs, Australas. J. Combin. 64 (2016) 444–457.
  44. L. Volkmann, Signed total Roman domination in digraphs, Discuss. Math. Graph Theory 37 (2017) 261–272.
    https://doi.org/10.7151/dmgt.1929
  45. L. Volkmann, The signed total Roman $k$-domatic number of a graph, Discuss. Math. Graph Theory 37 (2017) 1027–1038.
    https://doi.org/10.7151/dmgt.1970
  46. L. Volkmann, Signed total Roman $k$-domination in graphs, J. Combin. Math. Combin. Comput. 105 (2018) 105–116.
  47. L. Volkmann, The double Roman domatic number of a graph, J. Combin. Math. Combin. Comput. 104 (2018) 205–215.
  48. L. Volkmann, Double Roman domination and domatic numbers of graphs, Commun. Comb. Optim. 3 (2018) 71–77.
    https://doi.org/10.22049/CCO.2018.26125.1078
  49. L. Volkmann, The Italian domatic number of a digraph, Commun. Comb. Optim. 4 (2019) 61–70.
    https://doi.org/10.22049/CCO.2019.26360.1102
  50. L. Volkmann, The Roman $\{2\}$-domatic number of graphs, Discrete Appl. Math. 258 (2019) 235–241.
    https://doi.org/10.1016/j.dam.2018.11.027
  51. L. Volkmann, Italian domination in digraphs (J. Combin. Math. Combin. Comput.), to appear.
  52. L. Volkmann, The double Roman domatic number of a digraph, Discuss. Math. Graph Theory 40 (2020) 995–1004.
  53. L. Volkmann and D. Meierling, A note on the Roman domatic number of a digraph, Commun. Comb. Optim. 5 (2020) 19–26.
    https://doi.org/10.22049/CCO.2019.26419.1107
  54. Z. Xie, G. Hao and S. Wei, The Roman domination and domatic numbers of a digraph, Commun. Comb. Optim. 4 (2019) 47–59.
    https://doi.org/10.22049/CCO.2019.26356.1101
  55. B. Zelinka, $k$-domatic number of graphs, Czechoslovak Math. J. 33 (1983) 309–313.
  56. B. Zelinka, Domatic number and degrees of vertices of a graph, Math. Slovaca 33 (1983) 145–147.
  57. B. Zelinka, Domatic numbers of graphs and their variants: A survey, in: Domination in Graphs: Advanced Topics, T.W. Haynes, S.T. Hedetniemi and P.J. Slater (Ed(s)), (Marcel Dekker, Inc., New York 1998) 351–374.
Close