On the number of quasi‐kernels in digraphs
On the number of quasi‐kernels in digraphs
复制标题
关于有向图中的拟核数
DOI：
10.1002/jgt.10169
复制
发表时间：
2001
影响因子：
0.9
通讯作者：
Anders Yeo
中科院分区：
文献类型：
--
作者：
G. Gutin;K. Koh;E. G. Tay;Anders Yeo
有向图D =（V，A）的顶点集X是核，如果X是独立的（即，X的所有不同顶点对都是不相邻的），并且对于每个v ∈ V-X，存在x ∈ X使得vx ∈ A。一个有向图D =（V，A）的顶点集X是拟核，如果X是独立的，并且对每个v ∈ V-X，存在w ∈ V-X，x ∈ X使得vx ∈ A或vw，wx ∈ A。1974年，Chvátal和Lovász证明了每个有向图都有一个拟核。1996年，Jacob和Meyniel证明了如果一个有向图D没有核，则D至少包含三个拟核。我们刻画了具有一个和两个拟核的有向图，从而给出了一个有向图至少具有三个拟核的充要条件。特别地，我们证明了每一个阶至少为3的强有向图，它不是4圈，至少有三个拟核。© 2004 Wiley Periodicals，Inc.
A vertex set X of a digraph D = (V, A) is a kernel if X is independent (i.e., all pairs of distinct vertices of X are non‐adjacent) and for every v ∈ V‐X there exists x ∈ X such that vx ∈ A. A vertex set X of a digraph D = (V, A), is a quasi‐kernel if X is independent and for every v ∈ V‐X there exist w ∈ V‐X, x ∈ X such that either vx ∈ A or vw, wx ∈ A. In 1974, Chvátal and Lovász proved that every digraph has a quasi‐kernel. In 1996, Jacob and Meyniel proved that if a digraph D has no kernel, then D contains at least three quasi‐kernels. We characterize digraphs with exactly one and two quasi‐kernels, and, thus, provide necessary and sufficient conditions for a digraph to have at least three quasi‐kernels. In particular, we prove that every strong digraph of order at least three, which is not a 4‐cycle, has at least three quasi‐kernels. © 2004 Wiley Periodicals, Inc.