A Characterization of Separating Pairs and Triplets in a Graph.

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?

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1987
Accession Number
ADA184278

Entities

People

  • Arkady Kanevsky
  • Vijaya Ramachandran

Organizations

  • University of Illinois Urbana–Champaign

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Computational Science
  • Computations
  • Illinois
  • Intervals
  • Materials
  • Mathematical Analysis
  • Mathematics
  • Monitoring
  • Semiconductors
  • Separators
  • Triangles
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.