Domination Number of Harary Graph

Authors

  • M Ulul Albab Pendidikan Matematika - Universitas Islam Lamongan
  • Zainullah Zuhri Pendidikan Matematika - Institut Teknologi dan Sains Nahdlatul Ulama Pasuruan

DOI:

https://doi.org/10.30736/voj.v5i2.866

Keywords:

Dominating Set, Domination Number, k-Connected Graph, Harary Graph

Abstract

The domination number of graph  is the smallest cardinality of the domination set of graph G. A subset of a vertex set S of G is called the domination set if every element of  dominates every vertex of G, meaning that every vertex of G that is not an element of S is connected and one distance from S. The domination number has become interesting research studies on several graphs k -connected such as circulant graphs, grids, and wheels. This study aims to determine domination number of the other k-connected graph is Harary graph. The method used pattern detection and axiomatic deduction. The obtained results are new lemmas and theorems. The discussion obtained challenges new patterns of the smallest of domination number of Harary Graph, especially shape H_2,n, H_4,n, H_k,n and  for every n vertices, k even integer, and k<n.

Downloads

Download data is not yet available.

Author Biographies

M Ulul Albab, Pendidikan Matematika - Universitas Islam Lamongan

Departemen Pendidikan Matematilka UNISLA

Zainullah Zuhri, Pendidikan Matematika - Institut Teknologi dan Sains Nahdlatul Ulama Pasuruan

Departemen Pendidikan Matematika ITSNU Pasuruan

References

Alon, N., Balogh, J., Bollobás, B., & Szabó, T. (2002). Game domination number. Discrete Mathematics, 256(1–2), 23–33. https://doi.org/10.1016/S0012-365X(00)00358-7

Bonato, A., Lozier, M., Mitsche, D., Pérez-Giménez, X., & Prałat, P. (2015). The domination number of on-line social networks and random geometric graphs*. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9076, 150–163. https://doi.org/10.1007/978-3-319-17142-5_14

Chartrand, G., Haynes, T. W., Henning, M. A., & Zhang, P. (2019). From Domination to Coloring. http://link.springer.com/10.1007/978-3-030-31110-0

Chartrand, G., & Zhang, P. (2012). A First Course in Graph Theory. In Technometrics. Dover Publications, Inc. https://doi.org/10.1080/00401706.1988.10488342

Chudnovsky, M., Kim, R., Liu, C. H., Seymour, P., & Thomassé, S. (2018). Domination in tournaments. Journal of Combinatorial Theory. Series B, 130, 98–113. https://doi.org/10.1016/j.jctb.2017.10.001

Gonçalves, D., Pinlou, A., Rao, M., & Thomasse, S. (2011). The domination number of Grids*. SIAM J. Discrete Math., 25(3), 1443–1453. https://doi.org/10.1137/11082574

Gross, J. L., Yellen, J., & Anderson, M. (2019). Graph Theory and Its Applications (Third Edit). CRC Press.

Hao, G. (2017). On the domination number of digraphs. Ars Combin, 134, 51–60.

Harary, F. (1962). The maximum connectivity of a graph. Proc. Natl. Acad. Sci., U.S., 48, 1142–1146.

Haynes, T. W., Hedetniemi, S. T., & Henning, M. A. (2021). Models of Domination in Graphs. In Springer Cham (Vol. 66). https://doi.org/10.1007/978-3-030-51117-3_2

Haynes, T. W., Hedetniemi, S. T., & Henning, M. A. (2023). Domination in Graphs: Core Concepts. Springer Cham. https://doi.org/10.1007/978-3-031-09496-5

Haynes, T. W., Hedetniemi, S. T., & Slater, P. J. (1998). Fundamentals of Domination in Graphs. Marcel Dekker, Inc.

Henning, M. A., & Vuuren, J. H. van. (2022). Graph and Network Theory An Applied Approach using Mathematica. In Springer (Vol. 193, Issue C). Springer Nature Switzerland AG. https://doi.org/10.1016/S0167-5648(08)70928-6

Kalyan, K., & James, M. (2019). Domination Number of Sierpinski Cycle Graph of Order n. Journal of Computer and Mathematical Sciences, 10(4), 796–818. https://doi.org/10.29055/jcms/1066

Rad, N. J. (2009). Domination in Circulant Graphs. Analele Stiintifice Ale Universitatii Ovidius Constanta, Seria Matematica, 17(1), 169–176.

Saoub, K. R. (2021). Graph Theory : an introduction to proofs, algorithms, and applications. In Textbooks in Mathematics.

Snyder, K. (2011). c-Dominating Sets for Families of Graphs. University of Mary Washington. https://cas.umw.edu/dean/files/2011/10/KelsieSnyderMetamorphosis.pdf

Tanna, S. (2015). Broadcasting in Harary Graphs. Concordia University.

West, D. B. (2001). Introduction to Graph Theory (2nd Editio). Pearson Education, Inc.

Xu, K., & Li, X. (2018). On domination game stable graphs and domination game edge-critical graphs. Discrete Applied Mathematics, 250, 47–56. https://doi.org/10.1016/j.dam.2018.05.027

Downloads

PlumX Metrics

Published

2023-08-30

How to Cite

Albab, M. U., & Zuhri, Z. (2023). Domination Number of Harary Graph. Vygotsky: Jurnal Pendidikan Matematika Dan Matematika, 5(2), 135–144. https://doi.org/10.30736/voj.v5i2.866