Back to Search
Start Over
COMPLETELY DISCONNECTING THE COMPLETE GRAPH.
- Source :
-
SIAM Journal on Discrete Mathematics . 2000, Vol. 13 Issue 1, p33-47. 15p. - Publication Year :
- 2000
-
Abstract
- In this paper we consider procedures for completely disconnecting a complete graph on n vertices Kn. By this we simply mean that we wish to remove all of the edges of Kn in a sequence of steps by which the graph Kn is successively transformed into the empty graph on n vertices. The rules are that, on each step, we may remove at most one edge from each connected component of the present graph, and in addition we may impose a limit w on the maximum number of edges we can remove at a time. What is the minimum number of steps fw (n) it will take to completely disconnect Kn? The two cases considered are w = ∞ and w = 2. We show that the ratio of fw(n) to the number of edges of Kn is asymptotic to 2/3 in the first case and to 1/2 + λ(1 - λ) = .74194412 … in the second, where λ is the real root of the equation λ = 2(1 - λ)³. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 13
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 13220302
- Full Text :
- https://doi.org/10.1137/S0895480197326553