Eoh, Soogang; Kim, Suh-Ryung On chordal phylogeny graphs. (English) Zbl 1469.05063 Discrete Appl. Math. 302, 80-91 (2021). Summary: An acyclic digraph in which every vertex has indegree at most \(i\) and outdegree at most \(j\) is called an \(( i , j )\) digraph for some positive integers \(i\) and \(j\). S. C. Lee et al. [Discrete Appl. Math. 233, 83–93 (2017; Zbl 1372.05088)] studied the phylogeny graphs of \(( 2 , 2 )\) digraphs and gave sufficient conditions and necessary conditions for a \(( 2 , 2 )\) digraph to have a chordal phylogeny graph. Their work was motivated by problems related to evidence propagation in a Bayesian network for which it is useful to know which acyclic digraphs have chordal moral graphs (phylogeny graphs are called moral graphs in Bayesian network theory). In this paper, we extend their work.We completely characterize the phylogeny graph of a \(( 1 , i )\) digraph and an \(( i , 1 )\) digraph, respectively, for any positive integer \(i\). Then, we study phylogeny graphs of \(( 2 , j )\) digraphs to show that the phylogeny graph of a \(( 2 , j )\) digraph \(D\) is chordal if the underlying graph of \(D\) is chordal for any positive integer \(j\). Especially, we show that as long as the underlying graph of a \(( 2 , 2 )\) digraph is chordal, its phylogeny graph is not only chordal but also planar. Cited in 1 Document MSC: 05C20 Directed graphs (digraphs), tournaments 05C10 Planar graphs; geometric and topological aspects of graph theory Keywords:competition graph; moral graph; phylogeny graph; \( ( i; j )\) digraph; chordal graph; planar graph Citations:Zbl 1372.05088 PDFBibTeX XMLCite \textit{S. Eoh} and \textit{S.-R. Kim}, Discrete Appl. Math. 302, 80--91 (2021; Zbl 1469.05063) Full Text: DOI arXiv References: [1] Choi, Jihoon; Eoh, Soogang; Kim, Suh-Ryung, A new minimal chordal completion (2018), arxiv preprint arXiv:1810.05280 · Zbl 1409.05203 [2] Cohen, Joel E., Interval graphs and food webs: a finding and a problem, RAND Corp. Doc., 17696 (1968) [3] Cooper, Gregory F., The computational complexity of probabilistic inference using Bayesian belief networks, Artificial Intelligence, 42, 2-3, 393-405 (1990) · Zbl 0717.68080 [4] Hamelink, Ronald C., A partial characterization of clique graphs, J. Combin. Theory, 5, 2, 192-197 (1968) · Zbl 0167.22203 [5] Lauritzen, Steffen L.; Spiegelhalter, David J., Local computations with probabilities on graphical structures and their application to expert systems, J. R. Stat. Soc. Ser. B Stat. Methodol., 50, 2, 157-194 (1988) · Zbl 0684.68106 [6] Lee, Seung Chul; Choi, Jihoon; Kim, Suh-Ryung; Sano, Yoshio, On the phylogeny graphs of degree-bounded digraphs, Discrete Appl. Math., 233, 83-93 (2017) · Zbl 1372.05088 [7] Lick, Don R.; White, Arthur T., K-degenerate graphs, Canad. J. Math., 22, 5, 1082-1096 (1970) · Zbl 0202.23502 [8] Pearl, Judea, Fusion, propagation, and structuring in belief networks, Artificial Intelligence, 29, 3, 241-288 (1986) · Zbl 0624.68081 [9] Roberts, Fred S.; Sheng, Li, Phylogeny graphs of arbitrary digraphs, (Mathematical Hierarchies in Biology (1997)), 233-238 · Zbl 0887.05048 [10] Shachter, Ross D., Probabilistic inference and influence diagrams, Oper. Res., 36, 4, 589-604 (1988) · Zbl 0651.90043 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.