Article
A Linear Algorithm for the Neighbor-component Order Connectivity of Arbitrary Trees
Discrete Mathematics, Algorithms and Applications
(2024)
Abstract
The graph parameter neighbor-connectivity was first investigated by Gunther and Hartnell in 1987 and provides important information on how reliable a network can be when failures of a node may impact its neighbors. In this model, the failure of a node causes the deletion of its closed neighborhood, i.e., the node and its adjacent neighbors as well. The minimum number of closed neighborhoods whose removal results in an empty, complete, or disconnected subgraph is called the neighbor-connectivity of the graph. Since then component order connectivity models have emerged to address inadequacies in the traditional models of connectivity, namely, that in many real-world networks, when disconnecting a graph one may be left with components that are large enough to still be operable. By adapting neighbor-connectivity to a component order model, we introduced neighbor-component order connectivity, defined as the minimum number of closed neighborhoods that must be removed from a network to ensure all remaining components have order less than some given threshold value. Given a threshold value of one, the neighbor-component order connectivity of a graph is equivalent to the well-known parameter domination number of the graph. The problem of computing the domination number of an arbitrary graph is NP-hard, and computing neighbor-component order connectivity of a graph for an arbitrary threshold value is also NP-hard. Here, we present a linear-time algorithm for computing the neighbor-component order connectivity of an arbitrary tree for an arbitrary threshold value, thus generalizing the classic linear algorithm of Cockayne, Goodman, and Hedetniemi for the domination number of the tree.
Keywords
- Neighbor-component order connectivity,
- domination,
- component order connectivity,
- neighbor-connectivity,
- tree algorithm,
- complexity
Disciplines
Publication Date
January, 2024
DOI
10.1142/S179383092250183X
Citation Information
Kristi Luttrell. "A Linear Algorithm for the Neighbor-component Order Connectivity of Arbitrary Trees" Discrete Mathematics, Algorithms and Applications Vol. 16 Iss. 1 (2024) p. 2250183 ISSN: 1793-8317 Available at: http://works.bepress.com/kristi-luttrell/3/