论文标题
$ 3 $ -ANTI-CRICULANT DICRAPHS为$α$ - diperfect和be-Diperfect
$3$-anti-circulant digraphs are $α$-diperfect and BE-diperfect
论文作者
论文摘要
令$ d $为挖掘物。如果$ s $中的每对顶点在$ d $中不可变化，则$ v（d）$的子集$ s $是稳定的。如果$ v（d）$中的每个顶点完全属于$ \ nathcal {p} $，则$ d $ $ d $ of $ d $ of $ d $ of $ d $ of $ d $ of $ d $ of $ d $的集合是$ v（d）$的路径分区。我们说，如果$ p $的每条路径完全包含一个$ s $的一个顶点，则稳定的集合$ s $和一个路径分区$ \ mathcal {p} $是正交的。 Digraph $ d $满足$α$ -Property，如果对于每个最大稳定套件的$ s $ $ d $，则存在一个路径分区$ \ MATHCAL {p} $，因此$ s $和$ \ Mathcal {p} $是正交的。如果每一个$ d $ $ d $的子数据都满足$α$ property，则Digraph $ d $是$α$ diperfect。 1982年，克劳德·伯格（Claude Berge）提出了一种$α$ - 二级型挖掘的特征，就禁止的抗指导奇数循环而言。 2018年，Sambinelli，Silva和Lee提出了类似的猜想。 A digraph $D$ satisfies the Begin-End-property or BE-property if for every maximum stable set $S$ of $D$, there exists a path partition $\mathcal{P}$ such that (i) $S$ and $\mathcal{P}$ are orthogonal and (ii) for each path $P \in \mathcal{P}$, either the start or the end of $P$属于$ s $。如果每个引起的$ d $ $ d $ diperfect diperfect均为diperfect。 Sambinelli，Silva和Lee就禁止阻塞奇数循环而言，提出了对二级发射图的表征。在本文中，我们以$ 3 $ -Anti-Circulant Digraphs的方式验证了这两个猜想。我们还提供了一些$α$ diperfect和Be-Diperfect Digraphs的结构性结果。
Let $D$ be a digraph. A subset $S$ of $V(D)$ is a stable set if every pair of vertices in $S$ is non-adjacent in $D$. A collection of disjoint paths $\mathcal{P}$ of $D$ is a path partition of $V(D)$, if every vertex in $V(D)$ is exactly on a path of $\mathcal{P}$. We say that a stable set $S$ and a path partition $\mathcal{P}$ are orthogonal if each path of $P$ contains exactly one vertex of $S$. A digraph $D$ satisfies the $α$-property if for every maximum stable set $S$ of $D$, there exists a path partition $\mathcal{P}$ such that $S$ and $\mathcal{P}$ are orthogonal. A digraph $D$ is $α$-diperfect if every induced subdigraph of $D$ satisfies the $α$-property. In 1982, Claude Berge proposed a characterization for $α$-diperfect digraphs in terms of forbidden anti-directed odd cycles. In 2018, Sambinelli, Silva and Lee proposed a similar conjecture. A digraph $D$ satisfies the Begin-End-property or BE-property if for every maximum stable set $S$ of $D$, there exists a path partition $\mathcal{P}$ such that (i) $S$ and $\mathcal{P}$ are orthogonal and (ii) for each path $P \in \mathcal{P}$, either the start or the end of $P$ belongs to $S$. A digraph $D$ is BE-diperfect if every induced subdigraph of $D$ satisfies the BE-property. Sambinelli, Silva and Lee proposed a characterization for BE-diperfect digraphs in terms of forbidden blocking odd cycles. In this paper, we verified both conjectures for $3$-anti-circulant digraphs. We also present some structural results for $α$-diperfect and BE-diperfect digraphs.
