Categorical aspects of inducing closure operators on graphs by sets of walks. (English) Zbl 1391.68116

Summary: We study closure operators on graphs which are induced by sets of walks of identical lengths in these graphs. It is shown that the induction gives rise to a Galois correspondence between the category of closure spaces and that of graphs with walk sets. We study the two isomorphic subcategories resulting from the correspondence, in particular, the one that is a full subcategory of the category of graphs with walk sets. As examples, we discuss closure operators that are induced by path sets on some natural graphs on the digital plane \(\mathbb{Z}^2\). These closure operators are shown to include the well known Marcus-Wyse and Khalimsky topologies, thus indicating the possibility of using them as convenient background structures on the digital plane for the study of geometric and topological properties of digital images.


68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
06A15 Galois correspondences, closure operators (in relation to ordered sets)
18B99 Special categories
54A05 Topological spaces and generalizations (closure spaces, etc.)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI


[1] Adámek, J.; Herrlich, H.; Strecker, G. E., Abstract and concrete categories, (1990), Wiley & Sons · Zbl 0695.18001
[2] Ahlborn, T. J.; Bhargava, T. N., On topological spaces associated with digraphs, Acta Math. Acad. Sci. Hung., 19, 47-52, (1968) · Zbl 0164.24903
[3] Čech, E., Topological spaces, (Topological Papers of Eduard Čech, (1968), Academia), 436-472, ch. 28
[4] Čech, E., Topological spaces, (1966), Academia, (revised by Z. Frolík and M. Katětov) · Zbl 0141.39401
[5] Chvalina, J., Separation properties of topologies associated with digraphs, Scr. Fac. Sci. Nat. Univ. Purkyn. Brun., Math., 10, 8, 399-410, (1980)
[6] Engelking, R., General topology, (1977), Państwowe Wydawnictwo Naukowe
[7] Harrary, F., Graph theory, (1969), Addison-Wesley Publ. Comp
[8] Khalimsky, E. D.; Kopperman, R.; Meyer, P. R., Computer graphics and connected topologies on finite ordered sets, Topol. Appl., 36, 1-17, (1990) · Zbl 0709.54017
[9] Kiselman, C. O., Digital Jordan curve theorems, Lect. Notes Comput. Sci., 1953, 46-56, (2000) · Zbl 1043.68804
[10] Kong, T. Y.; Kopperman, R.; Meyer, P. R., A topological approach to digital topology, Am. Math. Mon., 98, 902-917, (1991) · Zbl 0761.54036
[11] Kong, T. Y.; Roscoe, W., A theory of binary digital pictures, Comput. Vis. Graph. Image Process., 32, 221-243, (1985) · Zbl 0624.68100
[12] Kong, T. Y.; Rosenfeld, A., Digital topology: introduction and survey, Comput. Vis. Graph. Image Process., 48, 357-393, (1989)
[13] Malitza, M., Topology, binary relations and internal operations, Rev. Roum. Math. Pures Appl., 33, 623-630, (1988)
[14] Marcus, D., A special topology for the integers (problem 5712), Am. Math. Mon., 77, 1119, (1970)
[15] Rosenfeld, A., Digital topology, Am. Math. Mon., 86, 621-630, (1979) · Zbl 0432.68061
[16] Šlapal, J., On closure operations induced by binary relations, Rev. Roum. Math. Pures Appl., 33, 623-630, (1988) · Zbl 0658.54002
[17] Šlapal, J., Convenient closure operators on \(\mathbb{Z}^2\), Lect. Notes Comput. Sci., 5852, 425-436, (2009) · Zbl 1267.68257
[18] Šlapal, J., Graphs with a path partition for structuring digital spaces, Inf. Sci., 233, 305-312, (2013) · Zbl 1284.05310
[19] Šlapal, J., Topological structuring of the digital plane, Discret. Math. Theor. Comput. Sci., 15, 165-176, (2013) · Zbl 1285.68190
[20] Šlapal, J., Path-set induced closure operators on graphs, Filomat, 30, 863-871, (2016) · Zbl 1462.05313
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.