Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-06T00:25:33.153Z Has data issue: false hasContentIssue false

Major n-connected graphs

Published online by Cambridge University Press:  09 April 2009

Ortrud R. Oellermann
Affiliation:
Department of Mathematics and Statistics, Western Michigan UniversityKalamazoo, Michigan 49008-5152, U.S.A.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

An induced subgraph H of connectivity (edge-connectivity) n in a graph G is a major n-connected (major n-edge-connected) subgraph of G if H contains no subgraph with connectivity (edge- connectivity) exceeding 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 kK(G), has order m. Moreover, upper and lower bounds on the order of such graphs G are established.

MSC classification

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 1989

References

[1]Chartrand, G. and Lesniak, L., Graphs and digraphs (2nd ed., Wadsworth & Brooks/Cole, Monterey, 1986).Google Scholar
[2]Mader, W., ‘Kritisch n-fach kantenzusammenhangende Graphen’, J. Combin. Theory Ser. B 40 (1986), 152158.CrossRefGoogle Scholar
[3]Matula, D. W., ‘Subgraph connectivity numbers of a graph’, Theory and applications of graphs, pp. 371383 (Springer-Verlag, Berlin 1978).CrossRefGoogle Scholar