On the Number of Minimum Size Separating Vertex Sets in a Graph.
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 k=2,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?
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1987
- Accession Number
- ADA184279
Entities
People
- Arkady Kanevsky
Organizations
- University of Illinois Urbana–Champaign