>
Fa   |   Ar   |   En
   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
  
 
 

Copyright 2023
Islamic World Science Citation Center
All Rights Reserved