A cactus theorem for end cuts

Author: 

Evangelidou, A
Papasoglu, P

Publication Date: 

1 January 2014

Journal: 

International Journal of Algebra and Computation

Last Updated: 

2020-06-03T07:59:13.85+01:00

Issue: 

1

Volume: 

24

DOI: 

10.1142/S0218196714500076

page: 

95-112

abstract: 

Dinits-Karzanov-Lomonosov showed that it is possible to encode all minimal edge cuts of a graph by a tree-like structure called a cactus. We show here that minimal edge cuts separating ends of the graph rather than vertices can be "encoded" also by a cactus. As a corollary, we obtain a new proof of Stallings' ends theorem. We apply our methods to finite graphs as well and we show that several types of cuts can be encoded by cacti. © 2014 World Scientific Publishing Company.

Symplectic id: 

460165

Submitted to ORA: 

Not Submitted

Publication Type: 

Journal Article