Distance ideals of digraphs

Carlos A. Alfaro, Teresa I. Hoekstra-Mendoza, Juan Pablo Serrano and Ralihe R. Villagrán

Applied Mathematics and Computation, 2025, vol. 500, issue C

Abstract: We focus on strongly connected, strong for short, digraphs since in this setting distance is defined for every pair of vertices. Distance ideals generalize the spectrum and Smith normal form of several distance matrices associated with strong digraphs. We introduce the concept of pattern which allow us to characterize the family Γ1 of digraphs with only one trivial distance ideal over Z. This result generalizes an analogous result for undirected graphs that states that connected graphs with one trivial ideal over Z consists of either complete graphs or complete bipartite graphs. It turns out that the strong digraphs in Γ1 consists in the circuit with 3 vertices and a family Λ of strong digraphs that contains complete graphs and complete bipartite graphs, regarded as digraphs. We also compute all distance ideals of some strong digraphs in the family Λ. Then, we explore the distance ideals of circuits, which turns out to be an infinite family of digraphs with unbounded diameter in Γ2, that is, digraphs with two trivial distance ideals.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300325001572
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:500:y:2025:i:c:s0096300325001572

DOI: 10.1016/j.amc.2025.129430

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().