The mincut graph of a graph

Kriel, Christo (School of Mathematics University of the Witwatersrand)
Mphako-Banda, Eunice (School of Mathematics University of the Witwatersrand)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 14, No 1 (2026): Electronic Journal of Graph Theory and Applications

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.