The mincut graph of a graph
Abstract
In this paper we introduce an intersection graph of a graph G , with vertex set the minimum edge-cuts of G . We find the minimum cut-set graphs of some well-known families of graphs and study the mincut graph as a graph operator. In doing so we follow the research programme on graph operators, as introduced by Prisner in the 1995 monograph "Graph Dynamics". Thus we ask and attempt to answer questions such as 'Which graphs appear as images of graphs?'; 'Which graphs are fixed under the operator?'; 'What happens if the operator is iterated?' We show that every graph is a minimum cut-set graph, henceforth called a mincut graph , of infinite depth and with an infinite number of roots.
Fields of Study & Subjects
Advanced Graph Theory Research
Graph Labeling and Dimension Problems
Limits and Structures in Graph Theory
Publication details
- Journal / source
- Electronic Journal of Graph Theory and Applications
- Publisher
- The Institute for Research and Community Services (LPPM) ITB
- Volume
- 14
- Issue
- 1
- Pages
- 33–33
- Publication date
- 22 April 2026
- Language
- EN