×

Integrity in graphs: Bounds and basics. (English) Zbl 0708.05031

Summary: The integrity of a graph G, denoted I(G), is defined by \(I(G)=\min \{| S| +m(G-S):\) \(S\subset V(G)\}\) where m(G-S) denotes the maximum order of a component of G-S; further an I-set of G is any set S for which the minimum is attained. Firstly some useful concepts are formalized and basic properties of integrity and I-sets identified. Then various bounds and interrelationships involving integrity and other well- known graphical parameters are considered, and another formulation introduced from which further bounds are derived. The paper concludes with several results on the integrity of circulants.

MSC:

05C35 Extremal problems in graph theory
PDFBibTeX XMLCite