The mincut graph: intersection graph and graph operator

Abstract

In this work we introduce and study an intersection graph of a graph G, with vertex set the minimum edge-cuts of G. We start our study of this new graph by finding the minimum cut-set graphs of some well-known families of graphs. We study the minimum cut-set graph, henceforth called a mincut graph, as a graph operator, using the well known line graph operator as a model. In doing so we follow the research programme on graph operators, as introduced by Prisner in the 1995 monograph “Graph Dynamics”. Thus we 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 mincut graph, and that every graph has an infinite number of roots under the operator. Furthermore, we show that every graph is part of an infinite sequence of mincut graphs under iteration of the operator. We characterise graphs that are fixed under the mincut operator and examine the properties of graphs that have a periodicity higher than one. We show that no graph diverges under iteration of the operator and we conjecture that most graphs converge to the null graph, K0. Finally we link the two fields of connectivity and graph colouring by using the bad colouring polynomial to count the number of mincuts of a graph, that is, the order of the mincut graph of a graph.