Yeni Bir Koşullu Bağlantı Ölçütü: Graflarda k-Toplam Baskınlık Ayrıt Bağlantılılığı

Abstract

Son yıllarda, graf teorisinde koşullu bağlantılılığın bir uzantısı olarak hâkimiyet temelli bağlantılılık kavramlarına artan bir ilgi gözlemlenmektedir. Bu çalışmada, toplam hâkimiyet kavramını içeren yeni bir koşullu bağlantılılık parametresi tanıtılmaktadır: k-toplam hâkimiyet kenar bağlantılılığı. 𝐺=(𝑉,𝐸) bağlantılı bir graf için bu parametre, grafın kenarlarından belirli bir alt kümenin çıkarılması sonucunda grafiğin kopması ve her bir bileşenin toplam hâkimiyet sayısının 𝑘 olması koşulunu sağlayan en küçük kenar kümesi olarak tanımlanır. Çalışmada özellikle 𝑘=2 durumu ele alınmış ve yol, çevrim ve tam grafikler gibi temel grafik sınıfları için bu ölçütün açık hesaplamaları sunulmuştur. Önerilen yaklaşım, hâkimiyet temelli kısıtlar altında ağların dayanıklılığını daha derinlemesine anlamaya katkı sağlamayı amaçlamaktadır.

Keywords

• Yumuşak hesaplama
• Koşullu bağlantılılık
• Baskınlık bağlantılılığı
• k-toplam baskınlık kenar bağlantılılığı

A Novel Conditional Connectivity Measure: k-Total Domination Edge Connectivity of Graphs

Abstract

In recent years, domination-based connectivity concepts have attracted growing interest as extensions of conditional connectivity in graph theory. In this study, we introduce a new conditional connectivity parameter that incorporates the notion of total domination, namely the k-total domination edge connectivity. Formally, for a connected graph G=(V,E), the parameter is defined as the smallest number of edges whose removal disconnects the graph in such a way that each resulting component has a total domination number equal to k. We particularly investigate the case k=2 and provide explicit calculations of this measure for fundamental graph classes such as paths, cycles, and complete graphs. The proposed approach aims to contribute to a deeper understanding of network robustness under domination-based constraints.

Keywords

• Graph connectivity
• Conditional connectivity
• Domination connectivity
• 2-total domination edge connectivity number
• k-total domination edge connectivity

References

1. Allan, R. B., Laskar, R., & Hedetniemi, S. 1984. A note on total domination. Discrete Mathematics, 49(1), 7-13.
2. Ba, L., Wu, H., Zhang, H. 2022. Star-structure connectivity of folded hypercubes and augmented cubes. The Journal of Supercomputing, 1-20.
3. Babikir, A., & Henning, M. A. 2022. Triangles and (total) domination in subcubic graphs. Graphs and Combinatorics, 38(2), 1-17.
4. Bertossi, A. A. 1986. Total domination in interval graphs. Information Processing Letters, 23(3), 131-134.
5. Bondy, J. A., & Murty, U. S. R. (2008). Graph theory. Springer.
6. Cheng, D. 2022. Extra Connectivity and Structure Connectivity of 2-Dimensional Torus Networks. International Journal of Foundations of Computer Science, 33(02), 155-173.
7. Cockayne, E. J., Dawes, R. M., & Hedetniemi, S. T. 1980. Total domination in graphs. Networks, 10(3), 211-219.
8. Diestel, R. (2017). Graph theory (5th ed.). Springer.

9. Dravec, T., Jakovac, M., Kos, T., & Marc, T. 2022. On graphs with equal total domination and Grundy total domination numbers. Aequationes mathematicae, 96(1), 137-146.
10. Ediz, S., Çiftçi, İ. 2022. On k-regular edge connectivity of chemical graphs. Main Group Metal Chemistry, 45(1), 106-110.
11. Goddard, W., & Henning, M. A. 2022. Domination and dominator colorings in planar graphs with small diameter. Discrete Applied Mathematics, 313, 80-92.
12. Guo, H., Sabir, E., Mamut, A. 2022. The g-extra connectivity of folded crossed cubes. Journal of Parallel and Distributed Computing, 166, 139-146.
13. Harary, F. 1983. Conditional connectivity. Networks, 13(3), 347-357.
14. Haynes, T. W., Hedetniemi, S. T., & Slater, P. J. (1998). Fundamentals of domination in graphs. CRC Press.
15. Henning, M. A., Kang, L., Shan, E., & Yeo, A. 2008. On matching and total domination in graphs. Discrete mathematics, 308(11), 2313-2318.
16. Kratsch, D. 2000. Domination and total domination on asteroidal triple-free graphs. Discrete Applied Mathematics, 99(1-3), 111-123.
17. Li, X., Zhou, S., Ma, T., Guo, X., Ren, X. 2022. The h-Restricted Connectivity of a Class of Hypercube-Based Compound Networks. The Computer Journal, 65(9), 2528-2534.
18. West, D. B. (2001). Introduction to graph theory (2nd ed.). Prentice Hall.
19. Yu, Z., Zhou, S., Zhang, H. 2022. Fault-Tolerant Strong Menger (Edge) Connectivity of DCC Linear Congruential Graphs. International Journal of Foundations of Computer Science, 1-14.
20. Zhang, M., Liu, H., & Lin, W. 2022. A unified approach to reliability and edge fault tolerance of cube-based interconnection networks under three hypotheses. The Journal of Supercomputing, 78(6), 7936-7947.
21. Zhang, M., Liu, H., Li, P. 2022. Embedded Edge-Connectivity Reliability Evaluation of Augmented Hypercube Interconnection Networks. International Journal of Foundations of Computer Science, 1-10.
22. Zhao, Y. Z., Li, X. J., Ma, M. 2022. Embedded connectivity of some BC networks. The Journal of Supercomputing, 1-14.
23. Zhu, B., Zhang, S., Zou, J., Ye, C. 2022. Two kinds of conditional connectivity of hypercubes. AKCE International Journal of Graphs and Combinatorics, 1-6.