Graphs, contraction mappings and minors
DOI:
https://doi.org/10.5564/jimdt.v6i1.3606Keywords:
categories, contraction, cyclic connectivity, graphs, minors, morphisms, relational systemsAbstract
This paper contains a review of topics on morphisms, contractions and minors, and several basic results that have been used repeatedly in the literature. Properties of contraction mappings and of cyclic connectivity are reviewed. The binary relation of minor inclusion is not far from being a partial order in any family of finite graphs. We also prove that if G is a 3-connected, internally 4-connected cubic graph that is not cyclically 4-connected then G ≃ K4 or G ≃ K2□K3. Diagrams as in other mathematical subjects such as algebra ought to be used for graph theory. Diagrams make concepts precise and clear, and avoid long verbal descriptions.
Downloads
125
References
[1] R.E.L. Aldred, "Cycles through seven vertices excluding an edge in 3-connected cubic graphs,"Ars Combinatoria,, 23B(1987), 79-86.
[2] R.E.L. Aldred, S. Bau and D.A. Holton, "Primitive graphs," Ars Combinatoria, 23B(1987),
183-193.
[3] R.E.L. Aldred, S. Bau, D.A. Holton and B.D. McKay, "Nonhamiltonian 3-connected cubic planar graphs," SIAM J. Discrete Math. (electronic), 13(1)(2000), 25-32. https://doi.org/10.1137/S0895480198348665
[4] S. Bau, "Cycles containing a set of elements in cubic graphs,"Austral. J. Comb., 2(1990), 57-76.
[5] S. Bau, "Cycles containing a set of six vertices and two edges in cubic planar graphs (Chinese with English abstract),"Pure and Applied Math. (Chinese), 11(2)(1995), 100-104.
[6] S. Bau, "Cycles with prescribed and forbidden sets of elements in cubic graphs," Graphs and Combin., 18(2002), 201-208. https://doi.org/10.1007/s003730200013
[7] S. Bau, "A generalization of the concept of Toeplitz graphs,"Mong. Math. J., 15(2011), 54-61.
[8] S. Bau and L.W. Beineke, "The decycling number of graphs,"Australas. J. Combin., 25(2002), 285-298.
[9] R. Diestel, Graph Theory, Springer Verlag, New York 2005.
[10] P. Hell and J. Nesetril, Graphs and Homomorphisms, Oxford University Press 2004.
[11] W. Imrich and S. Klavzar, Product Graphs, John Wiley Sons, New York 2000.
[12] M. Kilp and U. Knauer, "Graph operations and categorical constructions,"Acta et Comment.
Univ. Tartuensis de Math., 5(2001), 43-57. https://doi.org/10.12697/ACUTM.2001.05.04
[13] M. Kilp, U. Knauer and A.V. Mikhalev, Monoids, Acts and Categories, Walter de Gruyter, Berlin 2000.
[14] U. Knauer, "Semigroups and graph categories,"Lecture notes from a series of lectures presented at Chiang Mai University, Thailand, 2006.
[15] S. Mac Lane, Categories for the Working Mathematician, Springer-Verlag, New York 1971.
[16] W. Mader, "On -critically n-connected graphs,"in Progress in Graph Theory, ed. J.A. Bondy and U.S.R. Murty, Academic Press, Orlando 1984, 389-398.
[17] T. Politof and A. Satyanarayana, "The structure of quasi 4-connected graphs,"Discrete Math.,161(1996), 217-228. https://doi.org/10.1016/0012-365X(95)00229-P
[18] T. Tao and V.H. Vu, Additive Combinatorics, Cambridge University Press, Cambridge 2006.
[19] R. Thomas, "Recent excluded minor theorems for graphs,"Surveys in Combinatorics, 267(1999),201-222.
[20] C. Thomassen, "Kuratowski’s Theorem," J. Graph Theory, 5(3)(1981), 225-241. https://doi.org/10.1002/jgt.3190050304
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Sheng Bau
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
The authors grant the Journal of Institute of Mathemathics and Digital Technology a license to publish the article and identify itself as the original publisher.
Articles in the Journal of Institute of Mathemathics and Digital Technology are Open Access articles published under a Creative Commons Attribution-NonCommercial 4.0 International License - CC BY NC.
This license permits NonComericial use, distribution and reproduction in any medium, provided the original work is properly cited.
