Vertex and Mixed k-Diameter Component Connectivity
DOI:
https://doi.org/10.33043/N7CF7H5M2CAbstract
In the k-diameter component connectivity model a network is consider operational if there is a component with diameter at least k. Therefore, a network is in a failure state if every component has diameter less than k. In this paper we find the vertex variant of the k-diameter component connectivity parameter, which is the minimum number of vertex deletions in order to put a network into a failure state, for particular classes of graphs. We also show the mixed variant by allowing vertex and edge failures within the network. We show results for paths, cycles, complete, and complete bipartite graphs for both variants as well as perfect r-ary trees for the vertex variant.
References
L. Beineke and F. Harary. The connectivity function of a graph. Mathematika 14 (1967), 197–202.
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 (2006), 7–14.
F. Boesch, D. Gross, and C. Suffel, Component order connectivity. Proceedings of the Twenty-ninth Southeastern International Conference on Combinatorics. Graph Theory and Computing - Conger. Numen. 131 (1998), 145–155.
F. Boesch, A. Satyanarayana, and C. Suffel, A survey of some network reliability analysis and synthesis results. Networks 54 (2009), no. 2, 99–107.
A. Buzzard and N. Shank. The k-diameter component edge connectivity parameter. Involve 11 (2018), no. 5, 848–856.
F. Harary. Conditional connectivity. Networks 13 (1983), 347–357.
D. West. Introduction to graph theory. 2 ed., Prentice Hall, Upper Saddle River, NJ 07458, 2001.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Adam Buzzard, Nathan Shank
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
