论文标题
在程度界图的系统发育图上的结果扩展
Extensions of results on phylogeny graphs of degree bounded digraphs
论文作者
论文摘要
一个无环的图形，其中每个顶点最多都具有$ i $，最多$ j $的固定图称为$（i，j）$ digraph，对于某些正整数$ i $ $ $ $ $ $ $ $ $ $和$ j $。 digraph $ d $的系统发育图具有$ v（d）$作为顶点套件和边缘$ uv $，并且仅当以下一个是正确的：$（u，v）\ in（d）$; $（v，u）\ a（d）$; $（d）$和$（v，w）中的$（u，w）\在v（d）$中的某些$ w \ in（d）$中。图形$ g $是系统发育图（resp。\ an $（i，j）$系统发育图），如果有一个无环的digraph $ d $（resp. \ an $（i，j）$ digraph $ d $），以便$ d $的系统发育图$ d $是对$ g $ isomorphic to $ g $的。 Lee〜 {\ em等人}（2017）和Eoh and Kim（2021）研究了$（2,2）$系统发育图，$（1，J）$系统发育图，$（i，1）$（1）$系统发育图和$（2，J）$ PERLANY图。他们的工作是出于与证据传播有关的问题的激励，在贝叶斯网络中，知道哪些无环的挖掘物具有和弦道德图（在贝叶斯网络理论中称为道德图）很有用。在本文中，我们通过提供必要的和弦$（i，2）$系统发育图来扩展他们的工作。通过列出禁止的诱导子图，我们进一步提供了$（i，j）$系统发育图的必要条件。
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$. The phylogeny graph of a digraph $D$ has $V(D)$ as the vertex set and an edge $uv$ if and only if one of the following is true: $(u,v) \in A(D)$; $(v,u) \in A(D)$; $(u,w) \in A(D)$ and $(v,w) \in A(D)$ for some $w \in V(D)$. A graph $G$ is a phylogeny graph (resp.\ an $(i,j)$ phylogeny graph) if there is an acyclic digraph $D$ (resp.\ an $(i,j)$ digraph $D$) such that the phylogeny graph of $D$ is isomorphic to $G$. Lee~{\em et al.} (2017) and Eoh and Kim (2021) studied the $(2,2)$ phylogeny graphs, $(1,j)$ phylogeny graphs, $(i,1)$ phylogeny graphs, and $(2,j)$ phylogeny graphs. 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 by giving necessary conditions of chordal $(i,2)$ phylogeny graphs. We go further to give necessary conditions of $(i,j)$ phylogeny graphs by listing forbidden induced subgraphs.
