Strongly chordal digraphs and \Gamma-free matrices
From MaRDI portal
Publication:6324899
arXiv1909.03597MaRDI QIDQ6324899FDOQ6324899
Authors: Pavol Hell, César Hernández-Cruz, Jing Huang, Jephian Chin-Hung Lin 
Publication date: 8 September 2019
Abstract: We define strongly chordal digraphs, which generalize strongly chordal graphs and chordal bipartite graphs, and are included in the class of chordal digraphs. They correspond to square 0,1 matrices that admit a simultaneous row and column permutation avoiding the {Gamma} matrix. In general, it is not clear if these digraphs can be recognized in polynomial time, and we focus on symmetric digraphs (i.e., graphs with possible loops), tournaments with possible loops, and balanced digraphs. In each of these cases we give a polynomial-time recognition algorithm and a forbidden induced subgraph characterization. We also discuss an algorithm for minimum general dominating set in strongly chordal graphs with possible loops, extending and unifying similar algorithms for strongly chordal graphs and chordal bipartite graphs.
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Structural characterization of families of graphs (05C75) Perfect graphs (05C17)
This page was built for publication: Strongly chordal digraphs and $\Gamma$-free matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6324899)
