Narrow Results

For a given graph G = (V, E), its integrity is defined as I(G) = min_X⊂V {|X|+m(G−X)}, where m(G−X) denote the order of the largest component of G−X. In [9], authors discuss the minimum integrity of tree with given order and the maximum degree. In this paper, we point that the result in [9] is flawed and by elementary method characterize the structure of the minimum integrity tree and thus correct Theorem 4.1 in [9]. Finally, we give the construction method of this kind of extremal graph.

The integrity of a graph $G$ is defined as the minimum value of $\left|S\right|+m(G-S)$ taken over all $S\subseteq V(G)$, where $m(H)$ denotes the maximum cardinality of a component of graph $H$. In this paper, we investigate bounds on the maximum and minimum values of the weighted version of this parameter. We also consider the same question for the related parameter vertex-neighbor-integrity.