On the Integrity of Graphs

F. Li and X. Li (PRC)


Integrity, Maximum network, Nonlinear integer program ming, Saturated tree.


The integrity of a graph G = (V, E) is defined as I(G) = min{|S| + m(G - S) : S V (G)}, where m(G - X) denotes the order of the largest component in the graph G - X. This is a better parameter to measure the stability of a network G, as it takes into account both the amount of work done to damage the network and how badly the net work is damaged. In this paper, the maximum networks are obtained with prescribed order and integrity, and a method for constructing this sort of networks is also presented. Fi nally, we give the trees of minimum integrity with given order and maximum degree.

Important Links:

Go Back