Upper Bounds to the Number of Vertices in a k-Critically n-Connected Graph |
| |
Authors: | Matthias Kriesell |
| |
Institution: | (1) Institut für Mathematik (A), University of Hannover, Welfengarten 1, D-30167 Hannover, Germany. e-mail: kriesell@math.uni-hannover.de, DE |
| |
Abstract: | Let k≤n be positive integers. A finite, simple, undirected graph is called k-critically n-connected, or, briefly, an (n,k)-graph, if it is noncomplete and n-connected and the removal of any set X of at most k vertices results in a graph which is not (n−|X|+1)-connected. We present some new results on the number of vertices of an (n,k)-graph, depending on new estimations of the transversal number of a uniform hypergraph with a large independent edge set.
Received: April 14, 2000 Final version received: May 8, 2001 |
| |
Keywords: | , ,Connectivity, Hyperedge domination, Transversal number, Matching number |
本文献已被 SpringerLink 等数据库收录! |
|