Hostname: page-component-7b7567c8c-lpg2g Total loading time: 0 Render date: 2026-11-15T22:00:38.180Z Has data issue: false hasContentIssue false

Some Generalized Theorems on Connectivity

Published online by Cambridge University Press:  20 November 2018

R. E. Nettleton*
Affiliation:
The Rice Institute
Rights & Permissions [Opens in a new window]

Extract

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.

The “k-dense” subgraphs of a connected graph G are connected and contain neighbours of all but at most k-1 points. We consider necessary and sufficient conditions that a point be in Γk, the union of the minimal k-dense subgraphs. It is shown that Γk contains all the [m, k]-isthmuses” and [m, k]-articulators“— minimal subgraphs which disconnect the graph into at least k + 1 disjoint graphs—and that an [m, k]-isthmus or [m, k]-articulator of Γk disconnects G. We define “central points,” “degree” of a point, and “chromatic number” and examine the relationship of these concepts to connectivity. Many theorems contain theorems previously proved (1) as special cases.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1960