Accession Number:

ADA184279

Title:

On the Number of Minimum Size Separating Vertex Sets in a Graph.

Descriptive Note:

Technical rept.,

Corporate Author:

ILLINOIS UNIV AT URBANA APPLIED COMPUTATION THEORY GROUP

Personal Author(s):

Report Date:

1987-07-01

Pagination or Media Count:

16.0

Abstract:

Connectivity is an important graph property and there has been a considerable amount of work on vertex connectivity of graphs. An undirected graph G V,E is k-connected if for any subset V of k-1 vertices of G the subgraph induced by V-V is connected. A subset V of k vertices is a separating k-set if the subgraph induced by V-V is not connected. For k-1 the set V becomes a single vertex which is called an articulation point, and for k2,3 the sets V are called a separating pair and separating triplet, respectively. Efficient algorithms are available for finding all separating k-sets in k-connected undirected graphs for k or 3. The author addresses the following question what is the maximum number of separating k-sets in a k-connected undirected graph

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE