|
|||||
|
|
How to make a graph four-connected |
|
| Authors: | Ervin Győri Tibor Jordán |
| Affiliation: | (1) Mathematical Institute of the Hungarian Academy of Sciences, Reáltanoda u. 13-15, H-1053 Budapest, Hungary, HU;(2) CWI, Kruislaan 413, 1098 SJ, Amsterdam, The Netherlands. Current address: BRICS, Department of Computer Science, University of Aarhus, DK-8000 Aarhus C, Denmark, NL |
| Abstract: | (i) every 2-connected graph on n vertices can be made 4-connected by adding at most n new edges, and (ii) every 3-connected and 3-regular graph on n≥8 vertices can be made 4-connected by adding n/2 new edges. Received October 1995 / Revised version received March 1997 Published online March 16, 1999 |
| Keywords: | Mathematics Subject Classification (1991): 05C40 05C35 |
| 本文献已被 SpringerLink 等数据库收录！ | |