The mincut graph of a graph

Christo Kriel, Eunice Mphako-Banda

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.

Keywords


Connectivity; edge-cut set; mincut; intersection graph; graph operator

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2026.14.1.3

References

L. Cai, D. Corneil, and A. Proskurowski, A generalization of line graphs: (X,Y)-intersection graphs, J. Graph Theory 21 (3) (1996), 267–287.

L.S. Chandran and L.S. Ram, On the Number of Minimum Cuts in a Graph, SIAM J. Discrete Math. 18 (1) (2004), 177–194.

D. Chartrand, L. Lesniak, and P. Zhang, Graphs and Digraphs, 5th ed., CRC Press, Boca Raton, 2011.

E. Dinic, A. Karzanov, and M. Lomosonov, The structure of a system of minimal edge cuts of a graph. In A.A. Fridman, editor, Studies in Discrete Optimization, pages 290–306. Nauka, Moscow, 1976. Note: Translation at http://alexander-karzanov.net/ScannedOld/76_cactus_transl.pdf.

P. Erdos, A.W. Goodman, and L. Posa, The representation of a graph by set intersections, Can. J. Math. 18 (1966), 106–112.

L. Fleischer, Building Chain and Cactus Representations of All Minimum Cuts from Hao-Orlin in the Same Asymptotic Run Time, Journal of Algorithms 33 (1999), 51–72.

H.N. Gabow, A Matroid Approach to Finding Edge Connectivity and Packing Arborescences, Journal of Computer and System Sciences 50 (2) (1995), 259–273.

M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, 2nd ed., Elsevier, Amsterdam, 2004.

J.L. Gross, and J. Yellen, Handbook of Graph Theory, 1st ed., CRC Press, Boca Raton, 2004.

F. Harary, Graph Theory, Addison-Wesley, Reading, 1969.

A. Kanevsky, Graphs with odd and even edge connectivity are inherently different, Tech. report, TAMU-89-10, 1989.

J. Lehel, F. Maffray, and M. Preissmann, Graphs with largest number of minimum cuts, Discrete Appl. Math. 65 (1996), 387–407.

L. Lesniak, Results on the edge-connectivity of graphs, Discrete Math. 8 (1974), 351–354.

T.A. McKee and F.R. McMorris, Topics in Intersection Graph Theory, SIAM, Philadelphia, 1999.

M. Pal, Intersection Graphs: An Introduction, Annals of Pure and Applied Mathematics, 4 (1) (2013), 43–91.

E. Prisner, Graph Dynamics, Longman, Harlow, 1995.

E. Prisner, Line Graphs and Generalizations – A Survey. In G. Chartrand and M. Jacobson, editors, Surveys in Graph Theory, pages 193–229. Util. Math., Winnipeg, 1996.

A.C.M Van Rooi and H.S. Wilf, The interchange graph of a finite graph, Acta Math. Hungar. 16 (3–4) (1965), 263–269.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats