Generalized Bondage Number
The k-synchronous bondage number of a graph
DOI:
https://doi.org/10.33043/7dkds89xqmeAbstract
We investigate a generalization of the bondage number of a graph called the k-synchronous bondage number. The k-synchronous bondage number of a graph is the smallest number of edges that, when removed, increases the domination number by k. In this paper, we discuss the 2-synchronous bondage number and then generalize to the k -synchronous bondage number. We present k -synchronous bondage numbers for several graph classes and give bounds for general graphs. We propose this characteristic as a metric of the connectivity of a simple graph with possible uses in the field of network design and optimization.
References
A. Arora and K. Factor. Domination and network stability: an application. volume 175, pages 9–19. 2005. 36th Southeastern International Conference on Combinatorics, Graph Theory, and Computing.
D. Bauer, F. Harary, J. Nieminen, and C. Suffel. Domination alteration sets in graphs. Discrete Mathematics, 47:153–161, 1983.
L. Beineke and F. Harary. The connectivity function of a graph. Mathematika, 14(2):197–202, 1967.
F. Boesch, D. Gross, W. Kazmierczak, C. Suffel, and A. Suhartomo. Component order edge connectivity - an introduction. Proceedings of the Thirty-Seventh Southeastern International Conference on Combinatorics, Graph Theory and Computing - Conger. Numen., 178:7–14, 2006.
J.F. Fink, M. Jacobson, L. Kinch, and J. Roberts. The bondage number of a graph. Discrete Mathematics, 86(1-3):47–57, 1990.
D. Gross, M. Heinig, L. Iswara, W. Kazmierczak, K. Luttrell, J. Saccoman, and C. Suffel. A survey of component order connectivity models of graph theoretic networks. WSEAS Transactions on Mathematics, 12:895–910, September 2013.
D. Gross, M. Heinig, J. Saccoman, and C. Suffel. On neighbor component order edge connectivity. Congressus Numerantium, 223:17 – 32, 01 2015.
T. Haynes, S. Hedetniemi, and P. Slater. Fundamentals of Domination in Graphs. Marcel Dekker, New York, 1998.
F. Roberts. Graph theory and its applications to problems of society, volume 29 of CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1978.
E. Sampathkumar. Connectivity of a graph-a generalization. J. Comb. Inf. Syst. Sci, 9(2):71–78, 1984.
V. G. Vizing. An estimate of the external stability number of a graph. Dokl. Akad. Nauk SSSR, 164:729–731, 1965.
D. West. Introduction to Graph Theory. Prentice Hall, Upper Saddle River, NJ 07458, 2 edition, 2001.
J. Xu. On bondage numbers of graphs: A survey with some comments. International Journal of Combinatorics, 2013.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Nathan Shank
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
