The Iterated Local Transitivity Model for oriented graphs
Abstract
Transitivity in social and other complex networks describes the tendency for two nodes with a common neighbor to become adjacent. We propose a new model for complex networks based on transitivity, called the Iterated Local Transitivity Model for Oriented Graphs (ILTO). The model generalizes the Iterated Local Model for Tournaments (ILMT). As in ILMT, oriented graphs are generated iteratively by cloning nodes and their adjacencies, with arcs between clones oriented either as the corresponding arcs between their parents or in the reverse direction. This process produces dense oriented graphs and, under suitable conditions, graphs with high connectivity and small diameter. We analyze the universality properties of ILTO, showing that, for generating sequences with infinite support, the base oriented graph determines which oriented graphs appear as induced subgraphs, unlike in ILMT. We study motifs in ILTO and show that when the base graph is a tournament and the generating sequence has infinite support, the model generates quasirandom tournament sequences. Finally, we study domination numbers, the cop number, and the dichromatic number. We bound the cop number in terms of the independence number of the base graph and show that, for each fixed base graph, the dichromatic number is Θ(2t) after 2t consecutive 0-steps.
Related
- First Subconstituents of Orthogonal Graphs in Even Characteristic:Automorphisms, Cliques, Cores, and Binary Triple Transitivity
- ℱ-Transitivity of Backward Shifts on Lattice Graphs
- Optimal connectivity of second order iterated line graphs
- Local quadratic convergence of iterated correlation matrices: bounds and counterexamples
- Ramsey--Turán Factors of Non-directed Oriented Cycles in Oriented Graphs
BibTeX
@misc{bonato2026iterated,
title = {{The Iterated Local Transitivity Model for oriented graphs}},
author = {Anthony Bonato and MacKenzie Carr and Ketan Chaudhary and Trent G. Marbach and Teddy Mishura},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03843},
eprint = {2611.03843},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03843},
}
RIS
TY - UNPB
TI - The Iterated Local Transitivity Model for oriented graphs
AU - Anthony Bonato
AU - MacKenzie Carr
AU - Ketan Chaudhary
AU - Trent G. Marbach
AU - Teddy Mishura
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03843
UR - https://arxiv.org/abs/2611.03843
AB - Transitivity in social and other complex networks describes the tendency for two nodes with a common neighbor to become adjacent. We propose a new model for complex networks based on transitivity, called the Iterated Local Transitivity Model for Oriented Graphs (ILTO). The model generalizes the Iterated Local Model for Tournaments (ILMT). As in ILMT, oriented graphs are generated iteratively by cloning nodes and their adjacencies, with arcs between clones oriented either as the corresponding arcs between their parents or in the reverse direction. This process produces dense oriented graphs and, under suitable conditions, graphs with high connectivity and small diameter. We analyze the universality properties of ILTO, showing that, for generating sequences with infinite support, the base oriented graph determines which oriented graphs appear as induced subgraphs, unlike in ILMT. We study motifs in ILTO and show that when the base graph is a tournament and the generating sequence has infinite support, the model generates quasirandom tournament sequences. Finally, we study domination numbers, the cop number, and the dichromatic number. We bound the cop number in terms of the independence number of the base graph and show that, for each fixed base graph, the dichromatic number is Θ(2^t) after 2t consecutive 0-steps.
ER -