
doi: 10.2139/ssrn.6278085
This paper introduces a hierarchy of contractive endomorphisms on graphs, providing a rigorous framework for quantitative structural compression. We first define a general class of (m,n)-contractive endomorphisms, which map paths of length m to walks of length at most n, and prove that they form a semigroup under composition. To analyze the dynamics of iterated self-maps, we introduce a stricter condition, defining a uniformlyαcontractive endomorphism as one that compresses any path of length k to a walk of length at most αk + C, for some α ∈ (0,1) and constant C ≥ 0. This condition, analogous to Banach contractions in metric spaces, ensures that the contractive property is preserved under composition. Our main result demonstrates that the diameter of a finite graph under repeated application of a uniformly α-contractive endomorphism converges to a finite core diameter at a logarithmic rate, specifically O(log1/α D0), where D0 is the initial diameter. This work bridges algebraic graph theory and discrete dynamical systems, establishing a deterministic model for graph compression with provable guarantees.beginkeyword Graph Endomorphism, Metric Contraction, Banach FixedPoint Theorem, Discrete Dynamical Systems, Network Compression, Logarithmic Convergence, Algebraic Graph Theory
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
