On the Range of Possible Integrities of Graphs G(n, k)

We discuss the range of values for the integrity of a graphs G(n, k) where G(n, k) denotes a simple graph with n vertices and k edges. Let I _max(n, k) and I _min(n, k) be the maximal and minimal value for the integrity of all possible G(n, k) graphs and let the difference be D(n, k) = I _max(n, k) − I _min(n, k). In this paper we give some exact values and several lower bounds of D(n, k) for various values of n and k. For some special values of n and for s < n ^1/4 we construct examples of graphs G _n  = G _n (n, n + s) with a maximal integrity of I(G _n ) = I(C _n ) + s where C _n is the cycle with n vertices. We show that for k = n ²/6 the value of D(n, n ²/6) is at least \frac?6-13n{\frac{\sqrt{6}-1}{3}n} for large n.