RT journal article
T1 On the Packing Partitioning Problem on Directed Graphs
A1 Samadi, Babak
A1 González Yero, Ismael
A2 Matemáticas
K1 packing number
K1 packing partition number
K1 Cartesian product
K1 direct product
K1 lexicographic product
K1 strong product
K1 rooted product
K1 directed tree
AB This work is aimed to continue studying the packing sets of digraphs via the perspective ofpartitioning the vertex set of a digraph into packing sets (which can be interpreted as a type of vertexcoloring of digraphs) and focused on finding the minimum cardinality among all packing partitionsfor a given digraph D, called the packing partition number of D. Some lower and upper bounds onthis parameter are proven, and their exact values for directed trees are given in this paper. In the caseof directed trees, the proof results in a polynomial-time algorithm for finding a packing partition ofminimum cardinality. We also consider this parameter in digraph products. In particular, a completesolution to this case is presented when dealing with the rooted products.
PB MDPI
SN 2227-7390
YR 2021
FD 2021-12
LK http://hdl.handle.net/10498/26351
UL http://hdl.handle.net/10498/26351
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 13-nov-2026