Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.02848 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916348200747008 |
|---|---|
| author | Alfaro, Carlos A. Hoekstra-Mendoza, Teresa I. Serrano, Juan Pablo Villagrán, Ralihe R. |
| author_facet | Alfaro, Carlos A. Hoekstra-Mendoza, Teresa I. Serrano, Juan Pablo Villagrán, Ralihe R. |
| contents | 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 ${\mathbb Z}$.
This result generalizes an analogous result for undirected graphs that states that connected graphs with one trivial ideal over $\mathbb{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 circuits, which turn out to be an infinite family of minimal forbidden digraphs, as induced subdigraphs, for the strong digraphs in $Γ_1$.
This suggests that a characterization of $Γ_1$ in terms of forbidden induced subdigraphs is harder than using patterns. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_02848 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Distance ideals of digraphs Alfaro, Carlos A. Hoekstra-Mendoza, Teresa I. Serrano, Juan Pablo Villagrán, Ralihe R. Combinatorics 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 ${\mathbb Z}$. This result generalizes an analogous result for undirected graphs that states that connected graphs with one trivial ideal over $\mathbb{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 circuits, which turn out to be an infinite family of minimal forbidden digraphs, as induced subdigraphs, for the strong digraphs in $Γ_1$. This suggests that a characterization of $Γ_1$ in terms of forbidden induced subdigraphs is harder than using patterns. |
| title | Distance ideals of digraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2408.02848 |