On link-irregular digraphs
Journal of Combinatorial Mathematics and Combinatorial Computing · 31.03.2026 · 130 · 227-240
DOI: 10.61091/jcmcc130-15 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Combinatorial Mathematics and Combinatorial Computing, online erschienen am 31.03.2026. Verfasst von Alexander Bastien und 1 weiteren Autor:innen.
Abstract (Originalsprache)
We extend the study of link-irregular graphs to directed graphs (digraphs), where a digraph is link-irregular if no two vertices have isomorphic directed links. We establish that link-irregular digraphs exist on n vertices if and only if n ≥ 5, and prove that their underlying graphs must contain 3-cycles. We conjecture that link-irregular tournaments exist if and only if n ≥ 6, providing explicit constructions for n ≤ 8 and computational verification for n ≤ 100. We derive lower bounds on the minimum degree and outdegree required for link-irregularity, establish that almost all link-irregular digraphs are nonplanar, and prove that any link-irregular orientable graph admits a link-irregular labeling. Additionally, we construct explicit examples of link-irregular digraphs with constant outdegree and regular tournaments.
Zitieren
APA
Bastien, A., & Khormali, O. (2026). On link-irregular digraphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 130, 227-240. https://doi.org/10.61091/jcmcc130-15
Vancouver
Bastien A, Khormali O. On link-irregular digraphs. Journal of Combinatorial Mathematics and Combinatorial Computing. 2026;130:227-240. doi:10.61091/jcmcc130-15
BibTeX
@article{Bastien2026,
author = {Bastien, Alexander and Khormali, Omid},
title = {On link-irregular digraphs},
journal = {Journal of Combinatorial Mathematics and Combinatorial Computing},
year = {2026},
volume = {130},
pages = {227--240},
doi = {10.61091/jcmcc130-15}
}
EUVIMED