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) : Kanevsky,Arkady ; Ramachandran,Vijaya

PDF Url : ADA184278

Report Date : Jul 1987

Pagination or Media Count : 16

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 k=1 the set V' becomes a single vertex which is called an articulation point, and for k=2,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 :   *GRAPHICS, ALGORITHMS, SEPARATION, THEOREMS

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE