Extremal graphs in connectivity augmentation

Let A(n, k, t) denote the smallest integer e for which every k-connected gr aph on n vertices can be made (k + t)-connected by adding e new edges. We d etermine A(n, k, t) for all values of n, k, and t in the case of (directed and undirected) edge-connectivity and also for directed vertex-connectivity . For undirected vertex-connectivity we determine A(n, k, 1) for all Values of n and k. We also describe the graphs that attain the extremal values. ( C) 1999 John Wiley & Sons, Inc.