A linear algorithm for the neighbor-component order connectivity of arbitrary trees

被引:0
作者
Luttrell, Kristi [1 ]
机构
[1] Seton Hall Univ, Math Dept, 400 South Orange Ave, S Orange, NJ 07926 USA
关键词
Neighbor-component order connectivity; domination; component order connectivity; neighbor-connectivity; tree algorithm; complexity;
D O I
10.1142/S179383092250183X
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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.
引用
收藏
页数:12
相关论文
共 10 条