Strong chordality in tournaments and multipartite tournaments with possible loops
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908554753998848 |
|---|---|
| author | Hell, Pavol Hernández-Cruz, César Huang, Jing |
| author_facet | Hell, Pavol Hernández-Cruz, César Huang, Jing |
| contents | Strongly chordal digraphs are included in the class of chordal digraphs and generalize strongly chordal graphs and chordal bipartite graphs. They are the digraphs that admit a linear ordering of its vertex set for which their adjacency matrix does not contain the $Γ$ matrix as a submatrix. In general, it is not clear if these digraphs can be recognized in polynomial time. We focus on multipartite tournaments with possible loops. We give a polynomial-time recognition algorithm and a forbidden induced subgraph characterization of the strong chordality for each of the following cases: tournaments with possible loops, reflexive multipartite tournaments, irreflexive bipartite tournaments, irreflexive tournaments minus one arc, and balanced digraphs.
In addition, we prove that in a strongly chordal digraph the minimum size of a total dominating set equals the maximum number of disjoint in-neighborhoods, and this number can be calculated in linear time given a $Γ$-free ordering of the input graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_18541 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Strong chordality in tournaments and multipartite tournaments with possible loops Hell, Pavol Hernández-Cruz, César Huang, Jing Combinatorics 05C20, 05C75 Strongly chordal digraphs are included in the class of chordal digraphs and generalize strongly chordal graphs and chordal bipartite graphs. They are the digraphs that admit a linear ordering of its vertex set for which their adjacency matrix does not contain the $Γ$ matrix as a submatrix. In general, it is not clear if these digraphs can be recognized in polynomial time. We focus on multipartite tournaments with possible loops. We give a polynomial-time recognition algorithm and a forbidden induced subgraph characterization of the strong chordality for each of the following cases: tournaments with possible loops, reflexive multipartite tournaments, irreflexive bipartite tournaments, irreflexive tournaments minus one arc, and balanced digraphs. In addition, we prove that in a strongly chordal digraph the minimum size of a total dominating set equals the maximum number of disjoint in-neighborhoods, and this number can be calculated in linear time given a $Γ$-free ordering of the input graph. |
| title | Strong chordality in tournaments and multipartite tournaments with possible loops |
| topic | Combinatorics 05C20, 05C75 |
| url | https://arxiv.org/abs/2509.18541 |