Research Article
BibTex RIS Cite

Roman Domination in Mycielski Graphs: A Study of Some Graphs and a Heuristic Algorithm

Year 2024, , 494 - 502, 31.08.2024
https://doi.org/10.53433/yyufbed.1442759

Abstract

Let G=(V,E) be a graph. A function f:V→\{0,1,2\}, if ∀u for which f(u)=0 is adjacent to ∃v for which f(v)=2, is called a Roman dominating function, and called in short terms RDF. The weight of an RDF f is f(V)=∑_(v∈V)▒f(v) . The Roman domination number of a graph G, denoted by γ_R (G), is the minimum weight of an RDF on G. This paper presents the results for Roman domination numbers of the Mycielski graphs obtained through Mycielski's construction of the comet, double comet, and comb graphs. An algorithm to determine the Roman domination number of any given graph is also provided.

References

  • Chambers, E. W., Kinnersley, B., Prince, N., & West, D. B. (2009). Extremal problems for Roman domination. SIAM Journal on Discrete Mathematics, 23(3), 1575-1586. https://doi.org/10.1137/070699688
  • Cockayne, E. J., Dreyer Jr, P. A., Hedetniemi, S. M., & Hedetniemi, S. T. (2004). Roman domination in graphs. Discrete Mathematics, 278(1-3), 11-22. https://doi.org/10.1016/j.disc.2003.06.004
  • Dreyer, P. A. (2000). Applications and variations of domination in graphs. (PhD), Rutgers University, New Jersey.
  • Durgun, D. D., & Toprakkaya, E. N. (2021). Roman domination of the Comet, Double Comet, and Comb Graphs. arXiv preprint arXiv:2102.07902. https://doi.org/10.48550/arXiv.2102.07902
  • Durgun, D. D., & Toprakkaya, E. N. (2023). Roman domination on some graphs. Journal of Modern Technology and Engineering, 8(2), 96-104.
  • Haynes, T. W., Hedetniemi, S., & Slater, P. (1998). Fundamentals of domination in graphs. CRC Press. https://doi.org/10.1201/9781482246582
  • Henning, M. A., & Hedetniemi, S. T. (2003). Defending the Roman Empire - A new strategy. Discrete Mathematics, 266(1-3), 239-251. https://doi.org/10.1016/S0012-365X(02)00811-7
  • Kazemi, A. P. (2012). Roman domination and Mycielski’s structure in graphs. Ars Combinatoria, 106, 277-287.
  • Liedloff, M., Kloks, T., Liu, J., & Peng, S. (2008). Efficient algorithms for Roman domination on some classes of graphs. Discrete Applied Mathematics, 156(18), 3400-3415. https://doi.org/10.1016/j.dam.2008.01.011
  • Stewart, I. (1999). Defend the Roman Empire!, Scientific American, 281(6), 136-138. https://doi.org/10.1038/scientificamerican1299-136
  • West, D. B. (2001). Introduction to graph theory. Prentice Hall Upper Saddle River.

Mycielski Graflarda Roma Baskınlığı: Bazı Grafların ve Bir Sezgisel Algoritmanın Çalışması

Year 2024, , 494 - 502, 31.08.2024
https://doi.org/10.53433/yyufbed.1442759

Abstract

G=(V,E) bir graf olsun. f(u)=0 olan her u tepesinin, f(v)=2 olan en az bir v tepesine bitişik olması koşulunu karşılayan bir Roma baskınlık fonksiyonu (RDF) f:V→\{0,1,2\}. Bir RDF f’in ağırlığı f(V)=∑_(v∈V)▒f(v) . Bir G grafının Roma baskınlık sayısı, γ_R (G) ile gösterilir, G’de bir RDF’nin minimum ağırlığıdır. Bu çalışmada, Mycielski'nin kuyruklu yıldız, çift kuyruklu yıldız ve tarak graflarını oluşturmasıyla elde edilen Mycielski graflarının Roma baskınlık sayılarına ilişkin sonuçlarını sunmaktadır. Ayrıca, herhangi bir grafın Roma baskınlık sayısını belirleyen bir algoritma sağlanmıştır.

References

  • Chambers, E. W., Kinnersley, B., Prince, N., & West, D. B. (2009). Extremal problems for Roman domination. SIAM Journal on Discrete Mathematics, 23(3), 1575-1586. https://doi.org/10.1137/070699688
  • Cockayne, E. J., Dreyer Jr, P. A., Hedetniemi, S. M., & Hedetniemi, S. T. (2004). Roman domination in graphs. Discrete Mathematics, 278(1-3), 11-22. https://doi.org/10.1016/j.disc.2003.06.004
  • Dreyer, P. A. (2000). Applications and variations of domination in graphs. (PhD), Rutgers University, New Jersey.
  • Durgun, D. D., & Toprakkaya, E. N. (2021). Roman domination of the Comet, Double Comet, and Comb Graphs. arXiv preprint arXiv:2102.07902. https://doi.org/10.48550/arXiv.2102.07902
  • Durgun, D. D., & Toprakkaya, E. N. (2023). Roman domination on some graphs. Journal of Modern Technology and Engineering, 8(2), 96-104.
  • Haynes, T. W., Hedetniemi, S., & Slater, P. (1998). Fundamentals of domination in graphs. CRC Press. https://doi.org/10.1201/9781482246582
  • Henning, M. A., & Hedetniemi, S. T. (2003). Defending the Roman Empire - A new strategy. Discrete Mathematics, 266(1-3), 239-251. https://doi.org/10.1016/S0012-365X(02)00811-7
  • Kazemi, A. P. (2012). Roman domination and Mycielski’s structure in graphs. Ars Combinatoria, 106, 277-287.
  • Liedloff, M., Kloks, T., Liu, J., & Peng, S. (2008). Efficient algorithms for Roman domination on some classes of graphs. Discrete Applied Mathematics, 156(18), 3400-3415. https://doi.org/10.1016/j.dam.2008.01.011
  • Stewart, I. (1999). Defend the Roman Empire!, Scientific American, 281(6), 136-138. https://doi.org/10.1038/scientificamerican1299-136
  • West, D. B. (2001). Introduction to graph theory. Prentice Hall Upper Saddle River.
There are 11 citations in total.

Details

Primary Language English
Subjects Applied Mathematics (Other)
Journal Section Natural Sciences and Mathematics / Fen Bilimleri ve Matematik
Authors

Derya Dogan Durgun 0000-0002-9099-5448

Emre Niyazi Toprakkaya 0000-0003-1818-4330

Publication Date August 31, 2024
Submission Date February 25, 2024
Acceptance Date May 30, 2024
Published in Issue Year 2024

Cite

APA Dogan Durgun, D., & Toprakkaya, E. N. (2024). Roman Domination in Mycielski Graphs: A Study of Some Graphs and a Heuristic Algorithm. Yüzüncü Yıl Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 29(2), 494-502. https://doi.org/10.53433/yyufbed.1442759