
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) : Kanevsky,Arkady
PDF Url : ADA184279
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 vertex connectivity of graphs. An undirected graph G = (V,E) is kconnected if for any subset V' of k1 vertices of G the subgraph induced by VV' is connected. A subset V' of k vertices is a separating kset if the subgraph induced by VV' is not connected. For k1 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 ksets in kconnected undirected graphs for k or = 3. The author addresses the following question: what is the maximum number of separating ksets in a kconnected undirected graph?
Descriptors : *GRAPHS, EDGES, POINTS(MATHEMATICS), INEQUALITIES
Subject Categories : Numerical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE