Galois connections between sets of paths and closure operators in simple graphs. (English) Zbl 1407.05070

Summary: For every positive integer \(n\),we introduce and discuss an isotone Galois connection between the sets of paths of lengths \(n\) in a simple graph and the closure operators on the (vertex set of the) graph. We consider certain sets of paths in a particular graph on the digital line \(\mathbb Z\) and study the closure operators associated, in the Galois connection discussed, with these sets of paths. We also focus on the closure operators on the digital plane \(\mathbb Z^{2}\) associated with a special product of the sets of paths considered and show that these closure operators may be used as background structures on the plane for the study of digital images.


05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
06A15 Galois correspondences, closure operators (in relation to ordered sets)
Full Text: DOI


[1] Khalimsky E.D., Kopperman R., Meyer P.R., Computer graphics and connected topologies on finite ordered sets, Topology Appl., 1990, 36, 1-17 · Zbl 0709.54017
[2] Šlapal J., Graphs with a path partition for structuring digital spaces, Inf. Sciences, 2013, 233, 305-312 · Zbl 1284.05310
[3] Harrary F., Graph Theory, Addison-Wesley Publ. Comp., Reading, Massachussets, Menlo Park, California, London, Don Mills, Ontario, 1969
[4] Sabidussi G., Graph multiplication, Math. Z., 1960, 72, 446-457 · Zbl 0093.37603
[5] Cech E., Topological spaces, In: Topological Papers of Eduard Cech, Academia, Prague, 1968, ch. 28, 436-472
[6] Cech E., Topological Spaces (revised by Z. Frolík and M. Katětov), Academia, Prague, 1966
[7] Kong T.Y, Kopperman R., Meyer P.R., A topological approach to digital topology, Amer. Math. Monthly, 1991, 98, 902-917 · Zbl 0761.54036
[8] Engelking R., General Topology, Panstwowe Wydawnictwo Naukowe, Warszawa, 1977
[9] Davey B.A., Priestley H.A., Introduction to Lattices and Order, Cambridge University Press, Cambridge, 2002 · Zbl 1002.06001
[10] Klette R., Rosenfeld A., Digital Geometry - Geometric Methods for Digital Picture Analysis, Elsevier, Singapore, 2006
[11] Brimkov V.E., Klette R., Border and surface tracing - theoretical foundations, IEEE Trans. Patt. Anal. Machine Intell., 2008, 30, 577-590
[12] Khalimsky E.D., Kopperman R., Meyer P.R., Boundaries in digital plane, J. Appl. Math. Stochast. Anal., 1990, 3, 27-55 · Zbl 0695.54017
[13] Šlapal J., Jordan curve theorems with respect to certain pretopologies on Z2 Lect. Notes in Comput. Sci., 2009, 5810, 252-262 · Zbl 1261.68118
[14] Šlapal J., Convenient closure operators on Z2 Lect. Notes in Comput. Sci., 2009, 5852, 425-436 · Zbl 1267.68257
[15] Šlapal J., A digital analogue of the Jordan curve theorem, Discr. Appl. Math., 2004, 139, 231-251 · Zbl 1062.54001
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.