آمار
| تعداد نشریات | 7 |
| تعداد شماره‌ها | 102 |
| تعداد مقالات | 1,145 |
| تعداد مشاهده مقاله | 1,052,692 |
| تعداد دریافت فایل اصل مقاله | 874,168 |
A note on the small quasi-kernels conjecture in digraphs | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 14 مرداد 1402 اصل مقاله (298 K) | ||
| نوع مقاله: Short notes | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2023.28155.1459 | ||
| نویسندگان | ||
| Mostafa Blidia؛ M. Chellali* | ||
| LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria | ||
| چکیده | ||
| A subset $K$ of vertices of digraph $D=(V(D),A(D))$ is a kernel if the following two conditions are fulfilled: (i) no two vertices of $K$ are connected by an arc in any direction and (ii) every vertex not in $K$ has an ingoing arc from some vertex in $K.$ A quasi-kernel of $D$ is a subset $Q$ of vertices satisfying condition (i) and furthermore every vertex can be reached in at most two steps from $Q.$ A vertex is source-free if it has at least one ingoing arc. In 1976, P.L. Erdös and L.A. Székely conjectured that every source-free digraph $D$ has a quasi-kernel of size at most $\left\vert V(D)\right\vert /2.$ Recently, this conjecture has been shown to be true by Allan van Hulst for digraphs having kernels. In this note, we provide a short and simple proof of van Hulst's result. We additionally characterize all source-free digraphs $D$ having kernels with smallest quasi-kernels of size $\left\vert V(D)\right\vert /2.$ | ||
| کلیدواژه‌ها | ||
| Digraphs؛ kernel؛ quasi-kernel | ||
| مراجع | ||
|
[1] J. Bang-Jensen and G.Z. Gutin, Digraphs: Theory, Algorithms and Applications, Springer Science & Business Media, 2008.
[2] A. Kostochka, R. Luo, and S. Shan, Towards the small quasi-kernel conjecture, Electron. J. Combin. 29 (2022), no. 3, ID: #P3.49.
[3] A. van Hulst, Kernels and small quasi-kernels in digraphs, arXiv preprint arXiv:2110.00789 (2021). | ||
|
آمار تعداد مشاهده مقاله: 137 تعداد دریافت فایل اصل مقاله: 664 |
||