|
|
|
|
some new families of kp-digraphs
|
|
|
|
|
|
|
|
نویسنده
|
benítez-bobadilla germán ,galeana-sánchez hortensia ,hernández-cruz césar
|
|
منبع
|
communications in combinatorics and optimization - 2026 - دوره : 11 - شماره : 2 - صفحه:363 -386
|
|
چکیده
|
A kernel $n$ of a digraph $d$ is an independent set of vertices that is absorbent (for every vertex $uin v(d)setminus n$, there is a vertex $vin n$ such that $(u,v)in a(d)$). let $d$ be a digraph such that every proper induced subdigraph has a kernel. if $d$ has a kernel, then $d$ is a emph{kernel perfect digraph} (kp-digraph); otherwise, $d$ is a emph{critical kernel imperfect digraph} (cki-digraph). a digraph with the property $p$ is a digraph such that whenever a vertex reaches two other vertices through asymmetrical arcs, then these two vertices have the same out-neighborhood. in particular, digraphs whose asymmetrical part is a disjoint union of cycles have the property $p$. in this work, kp-digraphs with the property $p$ are characterized. as a consequence, kp-digraphs whose asymmetrical part is a hamiltonian cycle are also characterized. for digraphs with a hamiltonian cycle $gamma$ as their asymmetrical part and whose diagonals are symmetrical of length 2, two algorithms are presented; the first one determines whether a digraph is a kp-digraph or a cki-digraph, and the second constructs the kernel of the original digraph if it is a kp-digraph. as a consequence, a characterization of all cki-digraphs whose asymmetrical part is a hamiltonian cycle and whose diagonals are symmetrical of length 2 is shown.
|
|
کلیدواژه
|
kernel ,kernel perfect digraph ,circulant digraph ,kernel imperfect digraph
|
|
آدرس
|
universidad nacional autónoma de méxico, mexico, universidad nacional autónoma de méxico, instituto de matemáticas, mexico, universidad nacional autónoma de méxico, mexico
|
|
پست الکترونیکی
|
chc@ciencias.unam.mx
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|