On The Weighted Binding Number Of Graphs

Abstract

All networks such as logistics networks, internet networks, water and sewer networks, and electricity networks can be modeled with the help of graph theory. These networks need to be examined for similar situations such as reliability, durability and carrying capacity. These investigations can be achieved with the help of vulnerability parameters in graph theory. With the help of weighted graphs, weighted vulnerability measurements can be used. In unweighted graphs, vertex weights are assumed to be one. Thus, weighted vulnerability measurements are discriminative for both weighted and unweighted graphs. In this article, the definition of weighted binding number will be given for the first time. This concept is explained in detail. The algorithm and pseudo code for this weighted binding number will be given. It has been shown that weighted graphs are better discriminators in some cases. The importance of this parameter for some graphs is explained in detail.

Keywords

• Graph theory
• Edge integrity
• Algorithms

Çizgelerde Ağırlıklı Bağlama Sayısı Üzerine

Abstract

Lojistik ağları, internet ağları, su ve kanalizasyon ağları, elektrik ağları gibi tüm ağlar çizge teori yardımıyla modellenebilmektedir. Bu ağların güvenilirliği, sağlamlığı, taşıyabilme kapasiteleri gibi benzer durumlar için incelenmesi gerekmektedir. Bu incelemeler, çizge teorideki zedelenebilirlik parametreleri yardımıyla sağlanabilmektedir. Ağırlıklı çizgeler yardımıyla, ağırlıklı zedelenebilirlik ölçümleri kullanılabilmektedir. Ağırlıklı olmayan çizgelerde tepe ağırlıkları bir olarak kabul edilmektedir. Böylece ağırlıklı zedelenebilirlik ölçümleri hem ağırlıklı hem de ağırlıksız çizgeler için ayırt edici olmaktadırlar. Bu makalede ilk kez ağırlıklı bağlama sayısı tanımı verilecektir. Bu kavram detaylıca açıklanmıştır. Bu ağırlıklı bağlama sayısı için algoritma ve pseudo kod verilecektir. Ağırlıklı çizgelerin bazı durumlarda daha iyi bir ayırt edici olduğu verilmiştir. Bu parametrenin bazı çizgeler için önemi detaylıca açıklanmıştır.

Keywords

• Çizge teori
• Ayrıt bütünlüğü
• Algoritmalar

Ethical Statement

*Bu çalışma birinci yazarın yüksek lisans tezinden üretilmiştir.

References

1. [1] Barefoot, C. A., Entringer, R., Swart, H.C. 1987. Vulnerability in graphs- a comparative survey. J. Combin. Math. Combin. Comput., 1: 13–22. [2] Harary, F. Graph Theory. (1969). Addison-Wesley Publishing, 1-274 s. [3] Jung, H.A. 1978. On a class of posets and the corresponding comparability graphs. J. Combin. Theory Ser. B 24, 125–133. [4] Aslan, E. 2014. A Measure of Graphs Vulnerability: Edge Scattering Number. Bull.Soc.Math.Banja Luka, 4, 53 – 60.
2. [5] Aslan, E., Kürkçü, Ö. 2015. Edge Scattering Number of Gear Graphs. Bull.Soc.Math.Banja Luka, 5, 25-31.
3. [6] Woodall, D. R. 1973. The binding number of a graph and its Anderson number. J. Combinatorial Theory Ser. B 15 225–255.
4. [7] Li, F., Li., X. 2007. The neighbour-scattering number can be computed in polynomial time for interval graphs. Computers & Mathematics with Applications, 54 (5), 679-686.
5. [8] Ray, S., Kannan, R., Zhang, D., Jiang H. 2006. The weighted integrity problem is polynomial for interval graphs, Ars Combin., 79, 77-95.
6. [9] Arumugam, S., Velammal, S. 1998. Edge Domination in Graphs. Taiwanese Journal of Mathematics, 2(2) 173-179.
7. [10] Aytaç A., Turacı, T., Odabaş, Z.N. 2013. On the bondage number of middle graphs. Mathematical Notes, 93, 95–101.
8. [11] Aytaç A., Turacı, T., Odabaş, Z.N. 2016. Bondage and Strong-Weak Bondage Numbers of Transformation Graphs Gxyz, Inter. Jour.of Pure and App. Math., 106,(2), 689–698.

9. [12] Bagga, K.S., Beineke, L.W., Lipman M.J., Pippert, R.E. 1994. Edge-integrity: a survey. Discrete Mathematics, 124, 3-12.
10. [13] Kaval, B., Kırlangıç, A. 2024. Domination Scattering Number in Graphs. Journal of New Theory, 49, 53 – 61.
11. [14] Tokat, H., Kırlangıç, A. 2019. On the Domination Integrity. International Journal of Foundations of Computer Science, 30(5), 811-826.
12. [15] Aslan, E. Tosun, M.A., 2021. Computing the weighted neighbor isolated tenacity of interval graphs in polynomial time. Numerical Methods for Partial Differential Equations, 37(3), 2540-2549.
13. [16] Durgut, R., Turacı, T., Kutucu, H. 2019. A heuristic algorithm to find rupture degree in graphs. Turkish Journal of Electrical Engineering and Computer Sciences, 7: 3433 – 3441.
14. [17] Golumbic, M.C. 1980. Algorithmic Graph Theory and Perfect Graphs. Computer Science and Applied Mathematics Academic Press, New York.
15. [18] Li, F., Zhang, X., Broesmersma, H. 2019. A polynomial algorithm for weighted scattering number in interval graphs. Discrete Applied Mathematics, 264, 118-124.