Chordality of locally semicomplete and weakly quasi-transitive digraphs

DOI10.1016/J.DISC.2021.112362MaRDI QIDQ2022148zbMATH OpenOpenAlexFDO

Authors Jing Huang, Ying Ying Ye

Publication date 28 April 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.03568

zbMATH Keywords

chordal digraphforbidden subdigraph characterizationlocally semicomplete digraphweakly quasi-transitive digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Abstract: Chordal graphs are important in the structural and algorithmic graph theory. A digraph analogue of chordal graphs was introduced by Haskin and Rose in 1973 but has not been a subject of active studies until recently when a characterization of semicomplete chordal digraphs in terms of forbidden subdigraphs was found by Meister and Telle. Locally semicomplete digraphs, quasi-transitive digraphs, and extended semi-complete digraphs are amongst the most popular generalizations of semicomplete digraphs. We extend the forbidden subdigraph characterization of semicomplete chordal digraphs to locally semicomplete chordal digraphs. We introduce a new class of digraphs, called weakly quasi-transitive digraphs, which contains quasi-transitive digraphs, symmetric digraphs, and extended semicomplete digraphs, but is incomparable to the class of locally semicomplete digraphs. We show that weakly quasi-transitive digraphs can be recursively constructed by simple substitutions from transitive oriented graphs, semicomplete digraphs, and symmetric digraphs. This recursive construction of weakly quasi-transitive digraphs, similar to the one for quasi-transitive digraphs, demonstrates the naturalness of the new digraph class. As a by-product, we prove that the forbidden subdigraphs for semicomplete chordal digraphs are the same for weakly quasi-transitive chordal digraphs.

Recommendations

• Quasi-transitive digraphs and their extensions
• Quasi‐transitive digraphs
• Linkages in locally semicomplete digraphs and quasi-transitive digraphs
• Semicomplete compositions of digraphs
• On the structure of strong 3-quasi-transitive digraphs

Cites work

• A classification of locally semicomplete digraphs
• Chordal digraphs
• Classes of directed graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Kernels in quasi-transitive digraphs
• Kings in quasi-transitive digraphs
• Locally semicomplete digraphs: A generalization of tournaments
• On the structure of local tournaments
• Quasi‐transitive digraphs
• Strongly Connected Spanning Subdigraphs with the Minimum Number of Arcs in Quasi-transitive Digraphs
• Toward Characterization of Perfect Elimination Digraphs

Cited in

(3)

• Strict chordal digraphs viewed as graphs with distinguished edges
• Semi-strict chordal digraphs
• Semi-strict chordality of digraphs

This page was built for publication: Chordality of locally semicomplete and weakly quasi-transitive digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2022148)