J Austral Math Soc Ser A 47 pp43--52, 1989.
(Received 16 April 1987; revised 9 June 1988)
An induced subgraph H of connectivity (edge-connectivity) n ina graph G is a major n-connected (major n-edge-connected) subgraph of G if H contains no subgraph with connectivity (edge-connectivity) esceeding n and H has maximum order with respect to this property. An induced subgraph is a major (major edge-) subgraph if it is a major n-connected (major n-edge-connected) subgraph for some n. Let m be the maximum order among all major subgraphs of C. Then the major connectivity set K(G) of G is defined as the set of all n for which there exists a major n-connected subgraph of G having order m. The major edge-connectivity set is defined analogously. The connectivity and the elements of the major connectivity set of a graph are compared, as are the elements of the major connectivity set and the major edge-connectivity set of a graph. It is shown that every set S of nonnegative integers is the major connectivity set of some graph G. Further, it is shown that for each positive integer m exceeding every element of S, there exists a graph G such that every major k-connected subgraph of G, where k Î K(G), has order m. Moreover, upper and lower bounds on the order of such graphs G are established.
1980 AMS Subject Classification (1985 Revision): 05C40
Last Modified: Wed Feb 19 10:27:51 2003