# Accession Number:

## ADA184278

# Title:

## A Characterization of Separating Pairs and Triplets 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 algorithms for determining 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 k1 the set V becomes a single vertex which is called an articulation point, and for k2,3 the set V is 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 authors address the following question what is the maximum number of separating pairs and triplets in biconnected and triconnected undirected graphs, respectively

# Descriptors:

# Subject Categories:

- Numerical Mathematics