Article
The Relationship Between Neighbor-connectivity, Component Order Connectivity and Neighbor-component Order Connectivity
Congressus Numerantium
(2012)
Abstract
Given a graph G on n nodes and e edges, the component order connectivity parameter, κ c (k) (G) or simply κ c (k) , is defined as the minimum number of nodes that must be removed from a graph G in order to ensure that all remaining components have order less than some given threshold value, k. With neighbor-connectivity, the failure of a node causes the removal of adjacent neighbors as well. Thus, when a node is eliminated from the graph, the entire closed neighborhood of the node is also subverted in the graph. The neighbor-component order connectivity, κ nc (k) (G) or simply κ nc (k) , is defined as the minimum number of closed neighborhoods that must be removed from a graph G in order to ensure that all remaining components have order less than some given threshold value, k. Formulas for κ nc (k) have been derived for the complete graph, star graph, complete bipartite graph, path, and cycle; but the tree provides some very interesting realizability results. It has been shown that κ c (k) of an arbitrary tree lies between that of the star graph and the path. However, it has been observed that κ nc (k) of an arbitrary tree can be larger than that of the path. This paper will show that the upper bound for κ nc (k) of the tree is κ c (k) of the path.
Disciplines
Publication Date
January, 2012
Citation Information
Kristi Luttrell, Lakshmi Iswara, L. William Kazmierczak, Charles Suffel, et al.. "The Relationship Between Neighbor-connectivity, Component Order Connectivity and Neighbor-component Order Connectivity" Congressus Numerantium Vol. 212 (2012) p. 15 - 30 ISSN: 0384-9864 Available at: http://works.bepress.com/kristi-luttrell/5/