1graphs

1graphs, also known as functional graphs, are directed graphs in which each vertex has outdegree exactly one. Equivalently, they encode a function f from a finite vertex set to itself: f: V → V, with an edge from v to f(v) for every v in V. In this formulation, the graph is determined by the function values, and every vertex has a unique successor.

Structure in a finite 1graph is organized into components. Each connected component contains exactly one directed cycle, and all other vertices lie on directed trees that feed into the cycle. Edges progress toward the cycle under iteration of f, so every orbit eventually enters and remains on the cycle. Consequently, the long-term behavior of any vertex is to settle into a repeating cycle.

Properties and variations: The number of components equals the number of cycles in the graph. The cycle lengths and the shapes of the in-trees vary with the function f. If the graph is a permutation (a bijection), every vertex has in-degree 1 as well, and the component structure reduces to disjoint directed cycles with no trees attached. Some authors use the term 1graph for graphs where outdegree is at most 1, representing partial functions rather than total ones.

Applications and context: 1graphs model deterministic finite dynamical systems and iterated functions on finite sets. They are used to analyze cycle structures, preperiods, and basins of attraction. In probabilistic and combinatorial studies, random mappings (random 1graphs) yield results about expected cycle lengths and tree shapes, informing topics from hashing schemes to network dynamics.