On the Packing Partitioning Problem on Directed Graphs

Abstract

This work is aimed to continue studying the packing sets of digraphs via the perspective of partitioning the vertex set of a digraph into packing sets (which can be interpreted as a type of vertex coloring of digraphs) and focused on finding the minimum cardinality among all packing partitions for a given digraph D, called the packing partition number of D. Some lower and upper bounds on this parameter are proven, and their exact values for directed trees are given in this paper. In the case of directed trees, the proof results in a polynomial-time algorithm for finding a packing partition of minimum cardinality. We also consider this parameter in digraph products. In particular, a complete solution to this case is presented when dealing with the rooted products.

1. Introduction and Preliminaries

Graph partitions are universally extended procedures for equilibrating a property of a graph into smaller pieces of it. For instance, the graph partitioning problem is understood as that of dividing the vertices of a graph into sets of specified sizes such that few edges cross between sets. However, in our opinion, a graph partitioning problem should have a surname since one can partition a (directed) graph by using many different manners. Indeed, we can find countless ways of partitioning a (directed) graph according to features concerning the vertices and/or (arcs) edges of the (directed) graph.

Problems regarding the coloring of graphs are typically the most common, since finding a coloring of a (directed) graph consists of finding a partition of the graph into sets of vertices with a same color (independently of the colorability condition required). According to the wideness and popularity of a large number of the existent types of graph partitions, we shall not enumerate examples of partitions of any kind. Instead, we directly proceed to discuss the main goal of our exposition, which is aimed to develop some combinatorial properties of partitioning a directed graph (a digraph from now on) into packing sets, which, in fact, can be interpreted as a type of vertex coloring of the digraph.

Throughout this paper, we consider $D=(V(D),A(D))$ as a finite digraph with vertex set $V(D)$ and arc set $A(D)$ with neither loops nor multiple arcs (although pairs of opposite arcs are allowed). $G=(V(G),E(G))$ stands for a simple finite graph with vertex set $V(G)$ and edge set $E(G)$. We use [1,2] as references for some basic terminology and notation in digraphs and graphs, respectively, which are not explicitly defined here.

For any two vertices $u,v\in V(D)$, we write $uv$ as the arc with direction from u to v and say u is adjacent to v (u dominates v) or v is adjacent from u (v is dominated by u). For a vertex $v\in V(D)$, the out-neighborhood of v (in-neighborhood of v) is $N_D^{+}(v)=\{u\in V(D)\mid vu\in A(D)\}$ ($N_D^{-}(v)=\{u\in V(D)\mid uv\in A(D)\}$).

Moreover, $N_D^{+}[v]=N_D^{+}(v)\cup \{v\}$ ($N_D^{-}[v]=N_D^{-}(v)\cup \{v\}$) is the closed out-neighborhood (closed in-neighborhood) of v. The out-degree and in-degree of $v\in V(D)$ are ${deg}_D^{+}(v)=|N_D^{+}(v)|$ and ${deg}_D^{-}(v)=|N_D^{-}(v)|$, respectively. In addition, for a digraph D, ${\Delta }^{+}(D)$ and ${\delta }^{+}(D)$ represent the maximum and minimum out-degrees, and ${\Delta }^{-}(D)$ and ${\delta }^{-}(D)$ represent the maximum and minimum in-degrees of D. The vertex v is called a source (sink) if ${deg}_D^{-}(v)=0$ (${deg}_D^{+}(v)=0$). We say that a vertex v dominates all vertices in its closed out-neighborhood. The complement $\overline{D}$ of a digraph D is a digraph with the vertex set $V(D)$ in which $uv\in A(\overline{D})$ if and only if $uv\notin A(D)$.

The eccentricity of a vertex u in a graph G is ${\epsilon }_G(u)={max}_{v\in V(G)}{d}_G(u,v)$, where $d_G(u,v)$ stands for the distance between u and v. A digraph D is connected if its underlying graph is connected. A directed tree is an orientation of a tree (as a graph). A biorientation of a graph G is a digraph D, which is obtained from G by replacing each edge with end-points x and y by either the arcs $xy$ or $yx$, or the pair of arcs $xy$ and $yx$. A bipartite digraph is a biorientation of a bipartite graph.

A set $B\subseteq V(D)$ is a packing set, or simply a packing, in a digraph D if $N_D^{-}[u]\cap N_D^{-}[v]=\varnothing$ for any two distinct vertices $u,v\in B$. An equivalent definition of a packing in a digraph, and the one we prefer, is the following. A set $B\subseteq V(D)$ is a packing in a digraph D if $|N_D^{+}[v]\cap B|\le 1$ for all $v\in V(D)$. Notice that, among other things, this means that if a vertex v belongs to a packing set S in a digraph D, then none of its out-neighbors belongs to S. The packing number $\rho (D)$ is the largest possible number of vertices in a packing in D.

For all four standard products of digraphs D and F, the vertex set is $V(D)\times V(F)$. Their arc sets are defined as follows.

• In the Cartesian product $D\square F$, $(x,y)$ is adjacent to $(x^{\prime },y^{\prime })$ if “$x=x^{\prime }$ and $y{y}^{\prime }\in A(F)$” or “$x{x}^{\prime }\in A(D)$ and $y=y^{\prime }$”.
• In the direct product $D\times F$, $(x,y)$ is adjacent to $(x^{\prime },y^{\prime })$ if $x{x}^{\prime }\in A(D)$ and $y{y}^{\prime }\in A(F)$.
• The arc set of the strong product $G⊠H$ is the union of $A(D\square F)$ and $A(D\times F)$.
• $(x,y)$ is adjacent to $(x^{\prime },y^{\prime })$ in the lexicographic product $D\circ F$ if “$x{x}^{\prime }\in A(D)$” or “$x=x^{\prime }$ and $y{y}^{\prime }\in A(F)$”.

Note also that all these four products are associative, and only the first three are commutative. The map ${\pi }_D:V(D*F)\to V(D)$, defined by ${\pi }_D((x,y))=x$, is called a projection map onto D, for $*\in \{\square ,\times ,⊠,\circ \}$. The projection map onto F can be similarly defined. For a comprehensive treatment of the major topics in digraph products, we refer the reader to the books [3,4].

In this paper, our main focus is given to the vertex partitioning of a digraph D into packing sets. Such a vertex partition of any digraph D always exists, as $\{\{x\}\mid x\in V(D)\}$ is a trivial one. In fact, a challenging problem is to find a smallest partition of this type or its cardinality. More formally, we have the following definition.

Definition 1.

A packing partition, or P-partition for short, of a digraph D is a partition of $V(D)$ into packing sets. The packing partition number $\overrightarrow{p}(D)$ is the cardinality of a smallest possible P-partition of D.

Assume now that we have a system with a given number of radio stations. We need to assign a frequency to each station. Due to interference, the stations that are “close” to each other might need to receive different frequencies. Such problems are commonly arising while managing frequency assignments of base stations in cellular phone networks for instance. In a digraph model D of such a system, the vertices represent the radio stations, and an arc $xy$ indicates that the station x sends signals to the station y and that they are “near” to each other by using some kind of established “distance” framework.

For the sake of readability/realizability, any station might require receiving signals with different frequencies from its in-neighbors. This means that the vertices/stations in $N_D^{-}(v)$ receive different frequencies (labels that can be understood as positive integers) for each radio station (vertex) v. The set of all frequencies assigned to the whole set of radio stations clearly forms a partition of the set of radio stations by putting together in a same set of such partition those radio stations with the same frequency.

In this digraph model, and requiring a system with the smallest possible number of assigned frequencies, we can now readily observe that $\overrightarrow{p}(D^{-1})$ equals the minimum number of frequencies, which must be assigned to the stations in order to satisfy the above-mentioned conditions (here $D^{-1}$ is the digraph obtained by reversing the direction of every arc of D).

An equivalent definition for the parameter $\overrightarrow{p}(D)$ can be stated by using functions. Given a function $f:V(D)\to \{1,\cdots ,k\}$ of a digraph D, we set $U_i^f=\{v\in V(D)\mid f(v)=i\}$ for each $1\le i\le k$. We usually omit the superscript f if there is no ambiguity with respect to the function and write $f=(U_1,\cdots ,U_k)$.

Definition 2.

A function $f:V(D)\to \{1,\cdots ,k\}$ is a packing partitioning function, or PP-function for short, if it satisfies the following properties:

(a)$f(x)\ne f(x^{\prime })$ for any arc $x{x}^{\prime }$, and

(b)no vertex x is adjacent to two vertices $x^{\prime }$ and $x^{″}$ with $f(x^{\prime })=f(x^{″})$.

The minimum k for which a digraph D admits a PP-function $f:V(D)\to \{1,\cdots ,k\}$ represents the packing partition number of D and is denoted $\overrightarrow{p}(D)$.

Note that any PP-function $f:V(D)\to \{1,\cdots ,k\}$ gives a P-partition $\{U_1^f,\cdots ,U_k^f\}$ of the digraph D. Throughout this paper, by a $\rho (D)$-set and a $\overrightarrow{p}(D)$-partition, we mean a packing in D of maximum cardinality and a P-partition of D of minimum cardinality, respectively. A $\overrightarrow{p}(D)$-function will be a PP-function of D with $f(V(D))$ of minimum cardinality.

2. Packing Partition Number of Digraphs

The packing partition problem can be considered as a digraph counterpart of 2-distance coloring in graphs. The study of distance coloring was initiated by Kramer and Kramer ([5,6]) in 1969. A 2-distance coloring (or, 2DC for short) of a graph G is a mapping of $V(G)$ to a set of colors (nonnegative integers for convenience) in such a way that any two vertices of distance at most two have different colors. The minimum number of colors (nonnegative integers) k for which there is a 2DC is called the 2-distance chromatic number ${\chi }_2(G)$ of G.

Heggernes and Telle [7] showed that determining if a cubic graph can be 2-distance colored with four colors or less is NP-complete. We reduce this problem to its directed counterpart as follows. Recall first that, for a graph G, the complete biorientation $cb(G)$ of G is a digraph D obtained from G by replacing each edge $xy\in E(G)$ by the pair of arcs $xy$ and $yx$. Now, let G be a graph and let $f:V(G)\to \{1,\cdots ,k\}$ be a 2DC of G.

It is easy to see that $\{V_1^f,\cdots ,V_k^f\}$ is a P-partition of $cb(G)$, where $V_i^f=\{v\in V(G)\mid f(v)=i\}$ for each $1\le i\le k$. Conversely, any P-partition $\{B_1,\cdots ,B_k\}$ of $cb(G)$ results in a 2DC $f:V(G)\to \{1,\cdots ,k\}$ assigning i to all vertices x in $B_i$, for each $1\le i\le k$. This implies that ${\chi }_2(G)\le k$ if and only if $\overrightarrow{p}(cb(G))\le k$. Therefore, determining if a digraph whose underlying graph is cubic can be partitioned into at most four packing sets is NP-complete as well.

As a consequence, the problem of computing the packing partition number is NP-hard even when restricted to those digraphs whose underlying graphs are cubic. In this sense, it might be desirable to bound $\overrightarrow{p}$ with respect to several different invariants of the digraph or to give its exact value when dealing with some well-known families of digraphs.

We begin with some lower and upper bounds on the packing partition number of a digraph, which can directly be proved by its conceptual properties.

Proposition 1.

For any digraph D of order n, the following statements hold.

(i) $\overrightarrow{p}(D)\ge {\Delta }^{+}(D)+1$.

(ii) $n/\rho (D)\le \overrightarrow{p}(D)\le n-\rho (D)+1$.

These bounds are sharp.

Proof. 

(i) Let $\mathbb{P}$ be a $\overrightarrow{p}(D)$-partition and let $B\in \mathbb{P}$, and assume w.l.g. that $v\in B$ is a vertex of maximum out-degree. Hence, this means that none of the out-neighbors of v belongs to B, as well as, that each of these out-neighbors belongs to a different set of $\mathbb{P}$. That is, since $\mathbb{P}$ is a P-partition of D, there are $B_1,\cdots ,B_{{\Delta }^{+}(D)}\in \mathbb{P}\backslash \{B\}$ such that v has precisely one out-neighbor in any of them. Therefore, $\overrightarrow{p}(D)=|\mathbb{P}|\ge {\Delta }^{+}(D)+1$.

(ii) Assume $\mathbb{P}=\{B_1,\cdots ,B_{\overrightarrow{p}(D)}\}$ is the $\overrightarrow{p}(D)$-partition. Since every $B_i$ is a packing in D for $1\le i\le \overrightarrow{p}(D)$, it follows that $n={\sum }_{i=1}^{\overrightarrow{p}(D)}|B_i|\le \overrightarrow{p}(D)\rho (D)$. Hence, $\overrightarrow{p}(D)\ge n/\rho (D)$.

On the other hand, let B be a $\rho (D)$-set. Then, $\mathbb{P}=\{B\}\cup \{\{x\}\mid x\in V(D)\backslash B\}$ is a P-partition of D. Thus, $\overrightarrow{p}(D)\le |\mathbb{P}|=n-\rho (D)+1$.

The first bound is sharp for any digraph D having a vertex adjacent to every other vertex of D. The bounds given in $(ii)$ are sharp for any biorientation $b(K_n)$ of the complete graph $K_n$ with $\overrightarrow{p}(b(K_n))=n$. □

The following theorem shows that the lower bound given in Proposition 1 (i) always gives the exact values for the packing partition number of directed trees (as the extension of trees to digraphs). First, let $C{h}_T(v)$ be the set of children of a vertex v in a rooted tree T (as a graph).

Theorem 1.

For any directed tree T, $\overrightarrow{p}(T)={\Delta }^{+}(T)+1$.

Proof. 

By Proposition 1 (i), it only suffices to construct a P-partition of T of cardinality ${\Delta }^{+}(T)+1$. To do so, let r be a vertex in T of maximum out-degree. We consider the underlying tree $\widehat{T}$ of T and root it at r. Note that in $\widehat{T}$, any vertex at distance $p={\epsilon }_{\widehat{T}}(r)$ is a leaf (when $p\ge 1$). The result is trivial when $p=0$. Thus, we may assume that $p\ge 1$, and we construct a partitioning function f for T as follows. Let $U_i$ be the set of vertices at distance i from r in the tree $\widehat{T}$, with $1\le i\le p$.

In the directed tree T, we assign 0 to the vertex r and $1,\cdots ,{\Delta }^{+}(T)$ to its out-neighbors, so that all of them have a unique label. We also assign 1 to all the in-neighbors of r (if any). If $p=1$, then such an assignment clearly generates our required function. Hence, let $p\ge 2$. This means there exists a child of r in $\widehat{T}$, say u, that has at least one child. We consider two cases.

Case 1.$ru\in A(T)$. Then, $C{h}_{\widehat{T}}(u)=N_T^{+}(u)\cup (N_T^{-}(u)\backslash \{r\})$. Suppose that $i\in \{1,\cdots ,{\Delta }^{+}(T)\}$ has been assigned to u. We now assign deg${}_T^{+}(u)$ labels among $\{0,\cdots ,{\Delta }^{+}(T)\}\backslash \{i\}$ to the vertices in $N_T^{+}(u)$, so that any vertex in $N_T^{+}(u)$ has a unique label. Moreover, we assign one of these labels to all vertices in $N_T^{-}(u)\backslash \{r\}$.

Case 2.$ur\in A(T)$. Then, $C{h}_{\widehat{T}}(u)=(N_T^{+}(u)\backslash \{r\})\cup N_T^{-}(u)$. We assign deg${}_T^{+}(u)-1$ labels among the set $\{1,\cdots ,{\Delta }^{+}(T)\}\backslash \{i\}$ to the vertices in $N_T^{+}(u)\backslash \{r\}$, so that any of them has a unique label. We also assign 0 to all vertices in $N_T^{-}(u)$.

Iterating the process above for any other vertex in $C{h}_{\widehat{T}}(r)$ that has at least one child, we obtain an assignment of ${\Delta }^{+}(T)+1$ labels $\{0,\cdots ,{\Delta }^{+}(T)\}$ to the vertices in $\{r\}\cup U_1\cup U_2$. Repeating this process, we finally obtain such an assignment for all vertices of T. Note that

$(i)$ no two adjacent vertices have the same label, and

$(ii)$ no vertex is adjacent to at least two vertices with the same label.

Consequently, the partition $\{W_0,\cdots ,W_{{\Delta }^{+}(T)}\}$ generated by f is a P-partition of T, in which $W_i$ is the set of vertices having the label $0\le i\le {\Delta }^{+}(T)$. Thus, $\overrightarrow{p}(T)\le {\Delta }^{+}(T)+1$. This completes the proof. □

Let S be a vertex subset of a digraph D in which any two vertices are dominated by a vertex in S. It is easily checked that each PP-function of D must assign $|S|$ different labels to the vertices in S. Consequently, we find

$$\overrightarrow{p}(D)\ge max\{|S|:\mathrm{any} \mathrm{two} \mathrm{vertices} \mathrm{in} S \mathrm{are} \mathrm{dominated} \mathrm{by} \mathrm{some} \mathrm{vertex} \mathrm{in} S\}.$$

(1)

That this lower bound is tight may be seen as follows. Let D be any digraph with $V(D)=\{v_1,\cdots ,v_{|V(D)|}\}$ in which any two vertices are dominated by some vertex of D. We add $|V(D)|$ digraphs $D_1,\cdots ,D_{|V(D)|}$ such that $|V(D_1)|,\cdots ,|V(D_{|V(D)|})|\le |V(D)|$. Let $u_i$ be one vertex of $D_i$, for each $1\le i\le |V(D)|$. Assume $D^{\prime }$ is obtained from D and the digraphs $D_i$, by adding the arcs $u_i{v}_i$, for each $1\le i\le |V(D)|$.

Then, the function f assigning the labels $1,\cdots ,|V(D)|$ to the vertices of D and $1,\cdots ,|V(D_i)|$ to the vertices of $D_i$ so that $f(u_i)\ne f(v_i)$, for each $1\le i\le |V(D)|$, is a $\overrightarrow{p}(D^{\prime })$-function, which assigns $|V(D)|$ labels to the vertices of $D^{\prime }$. Moreover, it is easily observed that

$$|V(D)|=max\{|S|:\mathrm{any} \mathrm{two} \mathrm{vertices} \mathrm{in} S\subseteq V(D^{\prime }) \mathrm{are} \mathrm{dominated} \mathrm{by} \mathrm{some} \mathrm{vertex} \mathrm{in} S\}.$$

The lower bound given in (1) is also tight for some well-known families of digraphs, such as directed trees T, as it can be readily checked that this bound equals ${\Delta }^{+}(T)+1$ by Theorem 1. Moreover, it serves as the exact value of $\overrightarrow{p}$ for some other well-known families of digraphs.

Theorem 2.

If $\overline{D}$ is a bipartite digraph, then $\overrightarrow{p}(D)$ equals the maximum size of a vertex set S for which any two vertices in S are dominated by some vertex in S.

Proof. 

Let S be a set of vertices of maximum cardinality having the property that any two vertices of $D[S]$ are dominated by some vertex in S. As we already mentioned, any $\overrightarrow{p}(D)$-function assigns $|S|$ different labels to the vertices in S. In particular, we have $\overrightarrow{p}(D)\ge |S|$.

Let X and Y be the partite sets of $\overline{D}$. If $\overline{D}$ is a complete bipartite digraph (that is, the complete biorientation of a complete bipartite graph), then $D\cong cb(K_{|X|})+cb(K_{|Y|})$. Therefore, $\overrightarrow{p}(D)=max\{|X|,|Y|\}=|S|$. Thus, we may assume that $\overline{D}$ is not complete bipartite. This shows that there are some arcs in D from X to Y or vice versa. If any two vertices of D are simultaneously dominated by some vertex of D, then $\overrightarrow{p}(D)=|S|=|V(D)|$ and we are done.

Therefore, we assume that there exist two vertices $x^{*}$ and $y^{*}$ that are not dominated by any vertex of D. As the subdigraphs of D induced by X and Y are, respectively, the complete biorientations of the complete graphs $K_{|X|}$ and $K_{|Y|}$, it follows that $x^{*}$ and $y^{*}$ do not belong to a single partite set. Without loss of generality, $x^{*}\in X$ and $y^{*}\in Y$. Moreover, $N_D^{-}(x^{*})\cap Y=N_D^{-}(y^{*})\cap X=\varnothing$. We now set $X^{*}=\{x^{*}\in X\mid N_D^{-}(x^{*})\cap Y=\varnothing \}$ and $Y^{*}=\{y^{*}\in Y\mid N_D^{-}(y^{*})\cap X=\varnothing \}$. Without loss of generality, we may assume that $|Y^{*}|\ge |X^{*}|$.

Since any two vertices in S are dominated by some vertex in S, it follows that $S\cap X^{*}=\varnothing$ or $S\cap Y^{*}=\varnothing$. Choose any vertex $y^{*}\in Y^{*}$. If there exists a vertex $x\in X\backslash X^{*}$ such that x and $y^{*}$ are not dominated by any vertex in S, then x does not have any in-neighbor in Y. Hence, $x\in X^{*}$. This is a contradiction.

Taking into account the fact that the subdigraph of D induced by Y is the complete biorientation of a complete graph, we observe that each two vertices in $S\cup Y^{*}$ are dominated by some vertex in $S\cup Y^{*}$. We also have that any two vertices in $S\cup X^{*}$ are dominated by some vertex in $S\cup X^{*}$ by a similar argument. This implies that exactly one of the inclusions $X^{*}\subseteq S$ and $Y^{*}\subseteq S$ happens due to the maximality of S. This results in $Y^{*}\subseteq S$ since $|Y^{*}|\ge |X^{*}|$.

Let f be a function that assigns the labels $1,\cdots ,|Y^{*}|$ to the vertices in $Y^{*}$, $|Y^{*}|+1,\cdots ,|S|$ to the other vertices of S, and $1,\cdots ,|X^{*}|$ to the vertices in $X^{*}$. We observe that f is a PP-function of D assigning $|S|$ labels to the vertices of D. Therefore, $\overrightarrow{p}(D)\le |S|$. Consequently, $\overrightarrow{p}(D)=|S|$. □

3. Digraph Products

In this section, we study the packing partition number with respect to the four standard digraph products (Cartesian, direct, strong, and lexicographic). We also give an exact formula for this parameter when dealing with the rooted product of digraphs.

3.1. Cartesian and Strong Products

Let $\Lambda$ be the family of all digraphs D in which any two vertices are dominated by a vertex, simultaneously. It is readily seen that $\rho (D)=1$ ($\overrightarrow{p}(D)=n$) if and only if $D\in \Lambda$.

Theorem 3.

For any digraphs D and F,

$$max\{\overrightarrow{p}(D),\overrightarrow{p}(F)\}\le \overrightarrow{p}(D\square F)\le \overrightarrow{p}(D⊠F)\le \overrightarrow{p}(D)\overrightarrow{p}(F).$$

The equality $\overrightarrow{p}(D⊠F)=\overrightarrow{p}(D)\overrightarrow{p}(F)$ holds when $D\in \Lambda$ or $F\in \Lambda$.

Proof. 

The first inequality follows from the fact that the restriction of any $\overrightarrow{p}(D\square F)$-function to any copy of the digraphs D or F is a PP-function of D or F, respectively. The second inequality holds because any P-partition of $D⊠F$ is a P-partition of $D\square F$, as well.

For the third inequality, let $\mathbb{I}=\{I_1,\cdots ,I_{\overrightarrow{p}(D)}\}$ and $\mathbb{J}=\{J_1,\cdots ,J_{\overrightarrow{p}(F)}\}$ be a $\overrightarrow{p}(D)$-partition and a $\overrightarrow{p}(F)$-partition, respectively. Clearly, $\mathbb{P}=\{I_i\times J_j\mid 1\le i\le \overrightarrow{p}(D),1\le j\le \overrightarrow{p}(F)\}$ is a partition of $V(D⊠F)$. Suppose that $|N_{D⊠F}^{+}[(x,y)]\cap (I_i\times J_j)|\ge 2$ for some $(x,y)\in V(D⊠F)$, $1\le i\le \overrightarrow{p}(D)$ and $1\le j\le \overrightarrow{p}(F)$. Therefore, there are two distinct vertices $(x^{\prime },y^{\prime }),(x^{″},y^{″})\in N_{D⊠F}^{+}[(x,y)]\cap (I_i\times J_j)=(N_D^{+}[x]\cap I_i)\times (N_F^{+}[y]\cap J_j)$. Therefore, $|N_D^{+}[x]\cap I_i|\ge 2$ or $|N_F^{+}[y]\cap J_j|\ge 2$, a contradiction. This shows that, $\mathbb{P}$ is a P-partition of $D⊠F$, and thus $\overrightarrow{p}(D⊠F)\le |\mathbb{P}|=\overrightarrow{p}(D)\overrightarrow{p}(F)$.

We next assume that $F\in \Lambda$, and the case $D\in \Lambda$ can be symmetrically deduced. Suppose that $f=(U_1,\cdots ,U_{\overrightarrow{p}(D⊠F)})$ is a $\overrightarrow{p}(D⊠F)$-function. Suppose that there exists $1\le i\le \overrightarrow{p}(D⊠F)$ such that $U_i$ contains two distinct vertices $(x,y)$ and $(x,y^{\prime })$, for some $x\in V(D)$. With $F\in \Lambda$, it follows that $y,y^{\prime }\in N_F^{+}[y^{″}]$ for some $y^{″}\in V(F)$. This shows that $(x,y),(x,y^{\prime })\in N_{D⊠F}^{+}[(x,y^{\prime \prime })]\cap U_i$, in contradiction to the fact that $U_i$ is a packing in $D⊠F$. Therefore, $|U_i\cap (\{x\}\times V(F))|\le 1$ for each $x\in V(D)$ and $1\le i\le \overrightarrow{p}(D⊠F)$. This shows that f assigns precisely $|V(F)|$ labels to the vertices in $\{x\}\times V(F)$, for each $x\in V(D)$.

Choose two sets $I_i$ and $I_j$, for any $1\le i\ne j\le \overrightarrow{p}(D)$. Since $\mathbb{I}$ is a $\overrightarrow{p}(D)$-partition, it follows that

$(i)$ there are some vertices $x^{\prime }\in I_i$ and $x^{″}\in I_j$ such that $x^{\prime }{x}^{″}\in A(D)$, or

$(ii)$ some vertex $x\in V(D)$ is adjacent to at least two vertices $x^{\prime }\in I_i$ and $x^{″}\in I_j$.

Note that f assigns $|V(F)|$ labels to the vertices in $\{x^{\prime }\}\times V(F)$, as well as, to the vertices in $\{x^{″}\}\times V(F)$. Suppose that $f(\{x^{\prime }\}\times V(F))$ and $f(\{x^{″}\}\times V(F))$ are the sets of labels assigned to the vertices in $\{x^{\prime }\}\times V(F)$ and $\{x^{″}\}\times V(F)$, respectively. Assume that there exists a label $k\in f(\{x^{\prime }\}\times V(F))\cap f(\{x^{″}\}\times V(F))$. Therefore, $f((x^{\prime },y^{\prime }))=f((x^{″},y^{″}))=k$ for some $y^{\prime },y^{″}\in V(F)$. Note that each one of the items $(i)$ and $(ii)$ implies that $x^{\prime },x^{″}\in N_D^{+}[x]$ for some $x\in V(D)$.

On the other hand, there exists a vertex $y\in V(F)$ such that $y^{\prime },y^{″}\in N_F^{+}[y]$ because $F\in \Lambda$. Consequently, $(x^{\prime },y^{\prime }),(x^{″},y^{″})\in N_{D⊠F}^{+}[(x,y)]\cap U_k$. This contradicts the fact that f is a PP-function of $D⊠F$. The argument above guarantees that $U_i\cap U_j=\varnothing$, for every $1\le i\ne j\le \overrightarrow{p}(D⊠F)$. Therefore, $\overrightarrow{p}(D⊠F)\ge \overrightarrow{p}(D)|V(F)|=\overrightarrow{p}(D)\overrightarrow{p}(F)$. This completes the proof. □

We next see that the bounds above are tight. To this end, we consider the Cartesian product of two directed cycles $\overrightarrow{C_r}$ and $\overrightarrow{C_t}$, with $r,t\ge 3$ (that is, directed cycles in which every vertex has in-degree and out-degree equal to 1. It can be easily noted that

$$\overrightarrow{p}(\overrightarrow{C_n})=\left\{\begin{array}{cc}2,\hfill & \mathrm{if} n \mathrm{is} \mathrm{evev},\hfill \\ 3,\hfill & \mathrm{if} n \mathrm{is} \mathrm{odd}.\hfill \end{array}\right.$$

(2)

By using this fact, we obtain the next results.

Proposition 2.

For any $r,t\ge 2$, $\overrightarrow{p}(\overrightarrow{C_{2r}}\square \overrightarrow{C_{2t}})=\left\{\begin{array}{cc}3,\hfill & if r,t\equiv 0 (mod 3),\hfill \\ 4,\hfill & otherwise.\hfill \end{array}\right.$

Proof. 

Since ${\Delta }^{+}(\overrightarrow{C_{2r}}\square \overrightarrow{C_{2t}})=2$, by Proposition 1 (i), we have that $\overrightarrow{p}(\overrightarrow{C_{2r}}\square \overrightarrow{C_{2t}})\ge 3$. On the other hand, together $\overrightarrow{p}(D\square F)\le \overrightarrow{p}(D)\overrightarrow{p}(F)$ and the Equation (2) imply that $\overrightarrow{p}(\overrightarrow{C_{2r}}\square \overrightarrow{C_{2t}})\le 4$. Assume that $\overrightarrow{p}(\overrightarrow{C_{2r}}\square \overrightarrow{C_{2t}})=3$, and let $f:V(\overrightarrow{C_{2r}}\square \overrightarrow{C_{2t}})\to \{1,2,3\}$ be a $\overrightarrow{p}(\overrightarrow{C_{2r}}\square \overrightarrow{C_{2t}})$-function. Also, let $\overrightarrow{C_{2r}}=u_0{u}_1\cdots u_{2r-1}{u}_0$ and $\overrightarrow{C_{2t}}=v_0{v}_1\cdots v_{2t-1}{v}_0$.

Since $\overrightarrow{C_{2r}}\square \overrightarrow{C_{2t}}$ is vertex transitive, we may assume that $f(u_0,v_0)=1$. It must clearly happen (without loss of generality) that $f(u_0,v_1)=2$ and $f(u_1,v_0)=3$, and so $f(u_1,v_1)=1$. Now, $f(u_2,v_0)\ne 3$, which means either $f(u_2,v_0)=1$ or $f(u_2,v_0)=2$. If $f(u_2,v_0)=1$, then $N_D^{-}[(u_2,v_0)]\cap N_D^{-}[(u_1,v_1)]\ne \varnothing$, which is not possible. Thus, $f(u_2,v_0)=2$, which (together with $f(u_1,v_1)=1$) leads to $f(u_2,v_1)=3$. By a symmetric argument, we also obtain that $f(u_0,v_2)=3$, $f(u_1,v_2)=2$ and $f(u_2,v_2)=1$.

Consequently, it can be deduced that, in order to have a realization of the $\overrightarrow{p}(\overrightarrow{C_{2r}}\square \overrightarrow{C_{2t}})$-function f, the process described above must be consecutively repeated for each such $3\times 3$ pattern of $C_{2r}\square C_{2t}$. This means that, for the digraph $\overrightarrow{C_{2r}}\square \overrightarrow{C_{2t}}$ to have a packing partition of cardinality 3, it is necessary that both r and t will be congruent to 0 modulo 3. Therefore, $\overrightarrow{p}(\overrightarrow{C_{2r}}\square \overrightarrow{C_{2t}})=3$ if $r,t\equiv 0$ (mod 3). Otherwise, $\overrightarrow{p}(\overrightarrow{C_{2r}}\square \overrightarrow{C_{2t}})>3$. In this latter case, we deduce that $\overrightarrow{p}(\overrightarrow{C_{2r}}\square \overrightarrow{C_{2t}})=4$ for the other values of r and t. □

The proposition above shows the tightness of the second and third inequalities in Theorem 3, simultaneously. Here we observed that the third inequality in this theorem is sharp for an infinite family of digraphs different from those in $\Lambda$. Furthermore, we believe that the inequality usually gives the exact result.

By using similar arguments to the above ones, we can also prove the next result, which shows the tightness of the first inequality in Theorem 3.

Proposition 3.

For any $r,t\ge 1$, $\overrightarrow{p}(\overrightarrow{C_{3r}}\square \overrightarrow{C_{3t}})=3$.

3.2. Direct Product

The direct product is a natural environment for the open neighborhoods as $N_{D\times F}^{+}((x,y))=N_D^{+}(x)\times N_F^{+}(y)$ and $N_{D\times F}^{-}((x,y))=N_D^{-}(x)\times N_F^{-}(y)$, for all $(x,y)\in V(D\times F)$. Thus, the presence of an open version of the concept of packing (packing partition) can be expected. Brešar et al. [8] defined the open packing number in digraphs as follows. A subset B of $V(D)$ is an open packing of D if $N_D^{-}(u)\cap N_D^{-}(v)=\varnothing$, for every pair of distinct vertices u and v in B.

The open packing number ${\rho }^o(D)$ is the maximum cardinality of an open packing in D. In this sense, regarding the concept of open packing, partitioning the vertex set of a digraph into open packing sets can be interpreted as the open version of the problem discussed in this paper, which could be an interesting topic to be developed in its own. More formally, an open packing partition (OP-partition for short) of a digraph D is a vertex partition of D into open packing sets.

We call the minimum cardinality taken over all OP-partitions of D the open packing partition number of D and denote it by $\overrightarrow{p_o}(D)$. A $\overrightarrow{p_o}(D)$-partition is an OP-partition of D of cardinality $\overrightarrow{p_o}(D)$.

Clearly, $\overrightarrow{p_o}(D)\le \overrightarrow{p}(D)$ as any P-partition is an OP-partition of any digraph D. On the other hand, it can be noticed that there are digraphs whose open packing numbers equal the order of the digraphs. For instance, consider the directed cycle $\overrightarrow{C_n}$. It clearly happens that for any two vertices $u,v\in V(\overrightarrow{C_n})$, $N_{\overrightarrow{C_n}}^{-}(u)\cap N_{\overrightarrow{C_n}}^{-}(v)=\varnothing$. Thus, the whole set of vertices of any directed cycle forms an open packing, and thus $\overrightarrow{p_o}(\overrightarrow{C_n})=1$. In general, we observe that the statements “$\overrightarrow{p_o}(D)=1$”, “${\rho }^o(D)=|V(D)|$” and “${\Delta }^{+}(D)\le 1$” are equivalent.

We observe that the direct product $D\times F$ is empty (that is, $A(D\times F)=\varnothing$) if at least one of the factors D and F is empty. Therefore, $\overrightarrow{p}(D\times F)=1$ in such a situation. Thus, we may assume that both D and F are nonempty.

Theorem 4.

For any nonempty digraphs D and F,

$$max\{\overrightarrow{p_o}(D),\overrightarrow{p_o}(F)\}\le \overrightarrow{p_o}(D\times F)\le \overrightarrow{p}(D\times F)\le min\{\overrightarrow{p}(D)\overrightarrow{p_o}(F),\overrightarrow{p_o}(D)\overrightarrow{p}(F)\}.$$

Moreover, these bounds are sharp.

Proof. 

To prove the last inequality, let $\mathbb{I}=\{I_1,\cdots ,I_{\overrightarrow{p}(D)}\}$ and $\mathbb{J}=\{J_1,\cdots ,J_{\overrightarrow{p_o}(F)}\}$ be a $\overrightarrow{p}(D)$-partition and a $\overrightarrow{p_o}(F)$-partition of D, respectively. Clearly, $\mathbb{K}=\{I_i\times J_j\mid 1\le i\le \overrightarrow{p}(D),1\le j\le \overrightarrow{p_o}(F)\}$ is a partition of $V(D\times F)$. Note that $N_{D\times F}^{+}((x,y))=N_D^{+}(x)\times N_F^{+}(y)$, for all $(x,y)\in V(D\times F)$.

Suppose that $(x^{\prime },y^{\prime })$ and $(x^{″},y^{″})$ are distinct vertices belonging to $N_{D\times F}^{+}[(x,y)]\cap (I_i\times J_j)$, for some $(x,y)\in V(D\times F)$, $1\le i\le \overrightarrow{p}(D)$ and $1\le j\le \overrightarrow{p_o}(F)$. Assume that both $(x^{\prime },y^{\prime })$ and $(x^{″},y^{″})$ belong to the open neighborhood of $(x,y)$. This implies that $|N_D^{+}[x]\cap I_i|\ge 2$ or $y\in N_F^{-}(y^{\prime })\cap N_F^{-}(y^{″})$, which are contradictions to the facts that $I_i$ is a packing in D and that $J_j$ is an open packing in F.

Hence, we may assume that $(x^{\prime },y^{\prime })=(x,y)$ and $(x^{″},y^{″})\in N_{D\times F}^{+}((x,y))$. This implies that $x^{\prime }{x}^{″}\in A(D)$, contradicting the independence of $I_i$ in D. This shows that $\mathbb{K}$ is a P-partition of $D\times F$. Therefore, $\overrightarrow{p}(D\times F)\le |\mathbb{K}|=\overrightarrow{p}(D)\overrightarrow{p_o}(F)$. Interchanging the roles of D and F yields to $\overrightarrow{p}(D\times F)\le \overrightarrow{p_o}(D)\overrightarrow{p}(F)$. This results in the desired bound.

The middle inequality is an immediate consequence of the definitions. In order to prove the first inequality, we let $\mathbb{O}=\{O_1,\cdots ,O_{\overrightarrow{p_o}(D\times F)}\}$ be a $\overrightarrow{p_o}(D\times F)$-partition and let $y{y}^{*}\in A(F)$. For each $1\le i\le \overrightarrow{p_o}(D\times F)$, we define $A_i=\{x\in V(D)\mid (x,y^{*})\in O_i\}$. It is easily observed that $\mathbb{A}=\{A_1,\cdots ,A_{\overrightarrow{p_o}(D\times F)}\}\backslash \{\varnothing \}$ is a partition of $V(D\times F)$ of cardinality at most $\overrightarrow{p_o}(D\times F)$. Suppose now that $x\in V(D)$ is adjacent to two vertices $x_1,x_2\in V(D)$.

In particular, this implies that $(x,y)$ is adjacent to both $(x_1,y^{*})$ and $(x_2,y^{*})$ in $D\times F$. Therefore, $(x_1,y^{*})$ and $(x_2,y^{*})$ do not belong to a single member of $\mathbb{O}$. This shows that $x_1$ and $x_2$ belong to different members of $\mathbb{A}$. Thus, $\mathbb{A}$ is an OP-partition of $D\times F$. Therefore, $\overrightarrow{p_o}(D)\le |\mathbb{A}|\le \overrightarrow{p_o}(D\times F)$. A similar argument shows that $\overrightarrow{p_o}(F)\le \overrightarrow{p_o}(D\times F)$, leading to the first inequality.

That the third inequality is sharp may be seen by considering the direct product $\overrightarrow{C_r}\times \overrightarrow{C_s}$ when at least one of the integers r and s is even. Since $\overrightarrow{p_o}(\overrightarrow{C_r})=\overrightarrow{p_o}(\overrightarrow{C_s})=1$, and $\overrightarrow{p}(\overrightarrow{C_r})=2$ or $\overrightarrow{p}(\overrightarrow{C_s})=2$, by also using Proposition 1 (i), we have that

$$2={\Delta }^{+}(\overrightarrow{C_r}\times \overrightarrow{C_s})+1\le \overrightarrow{p}(\overrightarrow{C_r}\times \overrightarrow{C_s})\le min\{\overrightarrow{p}(\overrightarrow{C_r})\overrightarrow{p_o}(\overrightarrow{C_s}),\overrightarrow{p_o}(\overrightarrow{C_r})\overrightarrow{p}(\overrightarrow{C_s})\}=2,$$

which indicates the sharpness of the inequality.

We now consider the digraphs $cb(K_r)$ and $cb(K_s)$ for $r,s\ge 3$. It is easy to see that any two vertices of $cb(K_r)\times cb(K_s)$ are dominated by a third vertex. Consequently, $\overrightarrow{p_o}(cb(K_r)\times cb(K_s))=rs=\overrightarrow{p}(cb(K_r)\times cb(K_s))$. To see the sharpness of the first inequality, consider the digraphs $cb(K_2)$ and $cb(K_s)$ for $s\ge 3$. We notice that $\overrightarrow{p_o}(cb(K_2)\times cb(K_s))\le s$. On the other hand, $max\{\overrightarrow{p_o}(cb(K_2)),\overrightarrow{p_o}(cb(K_s))\}=s$. This completes the proof. □

We next obtain some other values for the packing partition number of direct product graphs that also show the tightness of the third inequality above.

Proposition 4.

Let $r,s$ be two integers.

(i) 

If $r,s\ge 2$, then $\overrightarrow{p}(\overrightarrow{P_r}\times \overrightarrow{P_s})=2$.

(ii) 

If $r,s\ge 3$, then $\overrightarrow{p}(\overrightarrow{C_r}\times \overrightarrow{C_s})=\left\{\begin{array}{cc}3,\hfill & if r,s are odd,\hfill \\ 2,\hfill & otherwise.\hfill \end{array}\right.$

Proof. 

(i) Since $\overrightarrow{p_o}(\overrightarrow{P_r})=\overrightarrow{p_o}(\overrightarrow{P_s})=1$ and $\overrightarrow{p}(\overrightarrow{P_r})=\overrightarrow{p}(\overrightarrow{P_s})=2$, by using Proposition 1 (i) and Theorem 4, we obtain

$$2={\Delta }^{+}(\overrightarrow{P_r}\times \overrightarrow{P_s})+1\le \overrightarrow{p}(\overrightarrow{P_r}\times \overrightarrow{P_s})\le min\{\overrightarrow{p}(\overrightarrow{P_r})\overrightarrow{p_o}(\overrightarrow{P_s}),\overrightarrow{p_o}(\overrightarrow{P_r})\overrightarrow{p}(\overrightarrow{P_s})\}=2.$$

(ii) In view of the proof of Theorem 4, we only need to prove the case in which both $r,s$ are odd. In such a situation, a similar argument gives

$$\overrightarrow{p}(\overrightarrow{C_r}\times \overrightarrow{C_s})\le min\{\overrightarrow{p}(\overrightarrow{C_r})\overrightarrow{p_o}(\overrightarrow{C_s}),\overrightarrow{p_o}(\overrightarrow{C_r})\overrightarrow{p}(\overrightarrow{C_s})\}=3.$$

However, it can be noted that $\overrightarrow{C_r}\times \overrightarrow{C_s}$ has always at least one subgraph, which is isomorphic to a cycle of odd order. Thus, towards constructing a packing partition for $\overrightarrow{C_r}\times \overrightarrow{C_s}$, we need at least three sets for any packing partition of such cycle. As a consequence, $\overrightarrow{p}(\overrightarrow{C_r}\times \overrightarrow{C_s})\ge 3$, which gives the desired equality for this case. □

3.3. Lexicographic Product

In what follows, we find the bounds of the packing partition number of the lexicographic product of any two digraphs.

Theorem 5.

For any digraphs D and F,

$${\Delta }^{+}(D)|V(F)|+\overrightarrow{p}(F)\le \overrightarrow{p}(D\circ F)\le \overrightarrow{p}(D)|V(F)|.$$

Moreover, these bounds are sharp.

Proof. 

If D is an empty digraph, then $\overrightarrow{p}(D\circ F)=\overrightarrow{p}(F)$. Hence, the lower and upper bounds are satisfied as ${\Delta }^{+}(D)=0$ and $\overrightarrow{p}(D)=1$ in this situation. Thus, we may assume that D is not empty. Now, let $V(F)=\{f_1,\cdots ,f_{|V(F)|}\}$, let d be a vertex of maximum out-degree in D and assume $N_D^{+}(d)=\{d_1,\cdots ,d_{{\Delta }^{+}(D)}\}$.

It clearly happens that every two vertices in $S={\bigcup }_{i=1}^{{\Delta }^{+}(D)}\{(d_i,f_1),\cdots ,(d_i,f_{|V(F)|})\}$ must belong to distinct sets in every P-partition for $D\circ F$. On the other hand, the vertices of the set $\{(d,f_1),\cdots ,(d,f_{|V(F)|})\}$ must belong to at least $\overrightarrow{p}(F)$ sets, which do not contain any vertex in S, in every P-partition for $D\circ F$. As a consequence, any P-partition for $D\circ F$ must have cardinality at least $|S|+\overrightarrow{p}(F)={\Delta }^{+}(D)|V(F)|+\overrightarrow{p}(F)$, which is the desired lower bound.

Assume D is a directed star $\overrightarrow{S_n}$ in which the central vertex is a sink and all the leaves are sources. We can form a P-partition for $D\circ F$ as follows. Let x be the center of $\overrightarrow{S_n}$ and let $V_L$ be the set of leaves of $\overrightarrow{S_n}$. If $V(F)=\{y_1,\cdots ,y_{|V(F)|}\}$ and $\mathbb{Q}=\{Q_1,\cdots ,Q_{|\overrightarrow{p}(F)|}\}$ is a $\overrightarrow{p}(F)$-partition, then we can observe that ${\mathbb{Q}}^{\prime }=\{\{(x,y_1)\},\cdots ,\{(x,y_{|V(F)|})\},V_L\times Q_1,\cdots ,V_L\times Q_{|\overrightarrow{p}(F)|}\}$ is a P-partition for $D\circ F$. Since $|{\mathbb{Q}}^{\prime }|=|V(F)|+\overrightarrow{p}(F)={\Delta }^{+}(D)|V(F)|$, in view of the lower bound, we deduce that $\overrightarrow{p}(D\circ F)=|V(F)|+\overrightarrow{p}(F)$.

On the other hand, let $V(F)=\{f_1,\cdots ,f_{|V(F)|}\}$ and let $\mathbb{B}=\{B_1,\cdots ,B_{\overrightarrow{p}(D)}\}$ be a $\overrightarrow{p}(D)$-partition Let $\mathbb{P}=\{B_i\times \{f_j\}\mid 1\le i\le \overrightarrow{p}(D),1\le j\le |V(F)|\}$. It is clear that $\mathbb{P}$ is a partition of $V(D\circ F)$. Suppose to the contrary that $|N_{D\circ F}^{+}[(x,y)]\cap (B_i\times \{f_j\})|\ge 2$, for some $(x,y)\in V(D\circ F)$, $1\le i\le \overrightarrow{p}(D)$ and $1\le j\le |V(F)|$. Therefore, $(x^{\prime },f_j),(x^{″},f_j)\in N_{D\circ F}^{+}[(x,y)]$ for some distinct vertices $x^{\prime },x^{″}\in B_i$. This implies that $x^{\prime },x^{″}\in N_D^{+}[x]\cap B_i$, which contradicts the fact that $B_i$ is a packing in D. Therefore, $\mathbb{P}$ is a P-partition of $D\circ F$. Thus, $\overrightarrow{p}(D\circ F)\le |\mathbb{P}|=\overrightarrow{p}(D)|V(F)|$.

That the upper bound is sharp may be seen as follows. We consider the directed cycle $\overrightarrow{C_n}$ on $n\equiv 0$ (mod 2) vertices. Let $x,y,z$ be three vertices of $\overrightarrow{C_n}$ such that $xy,yz\in A(\overrightarrow{C_n})$. Let $\mathbb{P}$ be a $\overrightarrow{p}(\overrightarrow{C_n}\circ F)$-partition for any digraph F. Clearly, the vertices in $\{(z,f_1),\cdots ,(z,f_{|V(F)|})\}$ must belong to $|V(F)|$ sets in $\mathbb{P}$ (not containing any vertex in $\{(y,f_1),\cdots ,(y,f_{|V(F)|})\}$). Furthermore, the vertices in $\{(y,f_1),\cdots ,(y,f_{|V(F)|})\}$ necessarily belong to $|V(F)|$ sets in $\mathbb{P}$ because x is adjacent to y. Therefore, $\overrightarrow{p}(\overrightarrow{C_n}\circ F)\ge 2|V(F)|=\overrightarrow{p}(\overrightarrow{C_n})|V(F)|$, resulting in the equality in the upper bound for $D=\overrightarrow{C_n}$. □

The existence of more than one sink in the first factor would result in a required larger number of sets in a P-partition for $D\circ F$ (when D is connected). To see this, let x and $x^{\prime }$ be two sinks of D. As D is connected, there is a path P connecting x to $x^{\prime }$ in the underlying graph of D. Since both x and $x^{\prime }$ are sinks of D, there exists a vertex $y\in V(P)$ with ${deg}_D^{+}(y)\ge 2$. This shows that $(y,f_1)$ is adjacent to all vertices in ${\{(y_1,f_i),(y_2,f_i)\}}_{i=1}^{|V(F)|}$, in which $y_1,y_2\in N_D^{+}(y)$. Thus, $\overrightarrow{p}(D\circ F)\ge 2|V(F)|+1>|V(F)|+\overrightarrow{p}(F)$.

3.4. Rooted Product

The rooted product graphs (see [9,10]) could be extended to digraphs as follows. A rooted digraph is a digraph in which one vertex is labeled in a special way to distinguish it from other vertices. The special vertex is called the root of the digraph. Let D be a labeled digraph on n vertices. Let $\mathcal{F}$ be a sequence of n rooted digraphs $F_1,\dots ,F_n$. The rooted product digraph $D(\mathcal{F})$ is the digraph obtained by identifying the root of $F_i$ with the $i^{\mathrm{th}}$ vertex of D.

Let $V(D)=\{u_1,\cdots ,u_n\}$ and let $\mathcal{F}$ be a sequence of n rooted digraphs $F_1,\dots ,F_n$ rooted at $v_1,\cdots ,v_n$, respectively. We observe that $D^{\prime }=({\{(u_i,v_i)\}}_{i=1}^n,\{(u_a,v_a)(u_b,v_b)\mid u_a{u}_b\in A(D)\})\cong D$ and $F_i^{\prime }=(\{u_i\}\times V(F_i),\{(u_i,v_b)(u_i,v_c)\mid v_b{v}_c\in A(F_i)\})\cong F_i$, for all $1\le i\le n$.

In what follows, we determine an exact formula for $\overrightarrow{p}(D(\mathcal{F}))$ in terms of the packing partition number of the product factors and the maximum out-degree of the roots $v_i$ of $V(F_i)$ having the largest packing partition number among those of $F_i$’s. In fact, we have the following theorem.

Theorem 6.

Let D be a digraph with $V(D)=\{u_1,\cdots ,u_n\}$. Let $\mathcal{F}$ be a sequence of n rooted digraphs $F_1,\dots ,F_n$ rooted at $v_1,\cdots ,v_n$, respectively. Then,

$$\overrightarrow{p}(D(\mathcal{F}))=max\{\overrightarrow{p}(D),\overrightarrow{p}(F_1),\cdots ,\overrightarrow{p}(F_n),{\Delta }^{*}+1\},$$

where ${\Delta }^{*}={max}_t\{{deg}_{D(\mathcal{F})}^{+}(v_t)\}$ taken over all t for which $\overrightarrow{p}(F_t)={max}_{1\le i\le n}\{\overrightarrow{p}(F_i)\}$.

Proof. 

We let $M=max\{\overrightarrow{p}(D),\overrightarrow{p}(F_1),\cdots ,\overrightarrow{p}(F_n),{\Delta }^{*}+1\}$ for the sake of convenience. Let $\mathbb{P}=\{B_1,\cdots ,B_{|\mathbb{P}|}\}$ be a $\overrightarrow{p}(D(\mathcal{F}))$-partition. For any subdigraph $K\in \{D,F_1,\cdots ,F_n\}$ of $D(\mathcal{F})$, it is easy to see that $\{B_1\cap V(K),\cdots ,B_{|\mathbb{P}|}\cap V(K)\}\backslash \{\varnothing \}$ is a P-partition of K of cardinality at most $|\mathbb{P}|$. Therefore, $\overrightarrow{p}(D),\overrightarrow{p}(F_i)\le |\mathbb{P}|=\overrightarrow{p}(D(\mathcal{F}))$ for all $1\le i\le n$. Moreover, $\overrightarrow{p}(D(\mathcal{F}))\ge {\Delta }^{+}(D(\mathcal{F}))+1\ge {\Delta }^{*}+1$ by Proposition 1 (i). Therefore, $\overrightarrow{p}(D(\mathcal{F}))\ge M$.

From now on, we assume that $f=(U_0,\cdots ,U_{\overrightarrow{p}(D)-1})$ and $g_i=(W_{0^i},\cdots ,W_{{(\overrightarrow{p}(F_i)-1)}^i})$ are a $\overrightarrow{p}(D)$-function and a $\overrightarrow{p}(F_i)$-function for $1\le i\le n$, respectively. Clearly,

$$g_i=(W_{0^i}^{\prime },\cdots ,W_{{(\overrightarrow{p}(F_i)-1)}^i}^{\prime })=(\{u_i\}\times W_{0^i},\cdots ,\{u_i\}\times W_{{(\overrightarrow{p}(F_i)-1)}^i})$$

is a $\overrightarrow{p}(F_i^{\prime })$-function for each $1\le i\le n$, and $f^{\prime }=(U_0^{\prime },\cdots ,U_{\overrightarrow{p}(D)-1}^{\prime })$ is a $\overrightarrow{p}(D^{\prime })$-function where $U_j^{\prime }=\{(u_i,v_i)\mid u_i\in U_j\}$ for each $1\le j\le \overrightarrow{p}(D)-1$.

Suppose that ${\Delta }^{*}={deg}_{D(\mathcal{F})}^{+}(v_t)={deg}_D^{+}(v_t)+{deg}_{F_t}^{+}(v_t)$ such that $\overrightarrow{p}(F_t)=$${max}_{1\le i\le n}\{\overrightarrow{p}(F_i)\}$. In order to complete the proof, we shall need the following claim. First, let

$$H=D(\mathcal{F})[V(D^{\prime })\cup V(F_t^{\prime })].$$

Claim 1.

If there is a P-partition of H of cardinality $M=max\{\overrightarrow{p}(D),\overrightarrow{p}(F_t),{\Delta }^{*}+1\}$, then there exists a P-partition of $D(\mathcal{F})$ of cardinality M.

Proof of Claim 1

Let h be a $\overrightarrow{p}(H)$-function assigning the labels $0,\cdots ,M-1$ to the vertices of H. By a relabeling of the indices of $U_0^{\prime },\cdots ,U_{\overrightarrow{p}(D)-1}^{\prime }$, we may assume that $(u_t,v_t)\in U_0^{\prime }$. We now define $h^{\prime }$ on $V(D(\mathcal{F}))$ as follows. First we take $h^{\prime }$ restricted to $V(H)$ as h, that is, $h^{\prime }{\mid }_{V(H)}=h$. Also, for any $(u_t,v_t)\ne (u_i,v_i)\in U_0^{\prime }$, we make $h^{\prime }((u_i,v))=h((u_t,v))$ for each $w\in V(F_i)$. In addition, consider the vertex $(u_j,v_j)\in U_r^{\prime }$, in which $0<r\le \overrightarrow{p}(D)-1$. We assume that $(u_j,v_j)\in W_{k^j}^{\prime }$, for some $0\le k\le \overrightarrow{p}(F_j)-1$. In such a case, we do the following assignments under $h^{\prime }$.

(a)

$h((u_j,v_j))$ to all vertices in $W_{k^j}^{\prime }$, and

(b)

$\overrightarrow{p}(F_j)-1$ labels from the sets of labels $\{0^t,\cdots ,{(\overrightarrow{p}(F_t)-1)}^t\}\backslash \{h((u_j,v_j))\}$ to the vertices in the sets $\{W_{0^j}^{\prime },\cdots ,W_{{(\overrightarrow{p}(F_j)-1)}^j}^{\prime }\}\backslash \{W_{k^j}^{\prime }\}$, in such a way that all vertices in each of these sets have a unique label.

It is not difficult to see that $h^{\prime }$ gives us a P-partition of $D(\mathcal{F})$ of cardinality M. □

By Claim 1, we only need to construct a P-partition of H of cardinality M. Notice that H can be considered as the union of D and $F_t$ having the vertex $u_t=v_t$ in common. Without loss of generality, we assume that $v_t\in U_0$ (as a vertex of D) and $v_t\in W_{0^t}$ (as a vertex of $F_t$). Moreover, we may assume that $\overrightarrow{p}(D)\ge \overrightarrow{p}(F_t)$. We shall deal with two possibilities.

Case 1.${deg}_{F_t}^{+}(v_t)\le \overrightarrow{p}(D)-{deg}_D^{+}(v_t)-1=k$. Note that $v_t$ has no out-neighbor in any k packing sets, say $U_1,\cdots ,U_k$, in D. We now define h as follows. As before, we first consider the restriction of h to $V(D)$, and make $h{\mid }_{V(D)}=f$. We may assume, without loss of generality, that $v_t$ has exactly one out-neighbor in $W_{1^t},\cdots ,W_{{deg}_{F_t}^{+}{(v_t)}^t}$.

We next consider that h assigns $0,1,\cdots ,{deg}_{F_t}^{+}(v_t)$ to vertices in $W_{0^t},W_{1^t},\cdots ,W_{{deg}_{F_t}^{+}{(v_t)}^t}$, respectively. If $\overrightarrow{p}(F_t)={deg}_F^{+}(v_t)+1$, then h gives us a P-partition of H of cardinality $\overrightarrow{p}(D)=M$. Thus, we may assume that $\overrightarrow{p}(F_t)>{deg}_{F_t}^{+}(v_t)+1$. In such a situation, we consider that h assigns the labels ${deg}_{F_t}^{+}(v_t)+1,\cdots ,\overrightarrow{p}(F_t)-1$ to the vertices in $W_{{({deg}_{F_t}^{+}(v_t)+1)}^t},\cdots ,W_{{(\overrightarrow{p}(F_t)-1)}^t}$, respectively. It is straightforward to check that $h:V(H)\to \{0,\cdots ,\overrightarrow{p}(D)-1\}$ gives us a P-partition of H of cardinality $\overrightarrow{p}(D)=M$.

Case 2.${deg}_{F_t}^{+}(v_t)>\overrightarrow{p}(D)-{deg}_D^{+}(v_t)-1=k$. We define $h^{\prime }$ as follows. Similarly, we do $h^{\prime }{\mid }_{V(D)}=f$. Assume that $h^{\prime }$ assigns the labels $0,1,\cdots ,k$ to all vertices in $W_{0^t},W_{1^t},\cdots ,W_{k^t}$, respectively. Moreover, $h^{\prime }$ assigns ${deg}_{F_t}^{+}(v_t)-k$ new labels ${(k+1)}^{″},\cdots ,{deg}_{F_t}^{+}{(v_t)}^{″}$ to all vertices in $W_{{(k+1)}^t},\cdots ,W_{{deg}_{F_t}^{+}{(v_t)}^t}$, respectively. We now consider two other possibilities.

Subcase 2.1.$\overrightarrow{p}(F_t)-{deg}_{F_t}^{+}(v_t)-1\le {deg}_D^{+}(v_t)$. If $\overrightarrow{p}(F_t)={deg}_{F_t}^{+}(v_t)+1$, then $h^{\prime }$ gives a P-partition of H of cardinality

$$\overrightarrow{p}(D)+{deg}_{F_t}^{+}(v_t)-k={deg}_{F_t}^{+}(v_t)+{deg}_D^{+}(v_t)+1={\Delta }^{*}+1=M.$$

If $\overrightarrow{p}(F_t)>{deg}_{F_t}^{+}(v_t)+1$, then we assume $h^{\prime }$ assigns the labels ${deg}_{F_t}^{+}(v_t)+1,\cdots ,\overrightarrow{p}(F_t)-1$ to the vertices in $W_{{({deg}_{F_t}^{+}(v_t)+1)}^t},\cdots ,W_{{(\overrightarrow{p}(F_t)-1)}^t}$, respectively. Thus, $h^{\prime }$ gives again a P-partition of H of cardinality

$$\overrightarrow{p}(D)+{deg}_{F_t}^{+}(v_t)-k={deg}_{F_t}^{+}(v_t)+{deg}_D^{+}(v_t)+1={\Delta }^{*}+1=M.$$

Subcase 2.2.$\overrightarrow{p}(F_t)-{deg}_{F_t}^{+}(v_t)-1>{deg}_D^{+}(v_t)$. Now, let $l=\overrightarrow{p}(F_t)-{deg}_{F_t}^{+}(v_t)-1-{deg}_D^{+}(v_t)$. Assume $h^{\prime }$ assigns $k+1,\cdots ,k+{deg}_D^{+}(v_t)=\overrightarrow{p}(D)-1$ to the vertices in $W_{{({deg}_{F_t}^{+}(v_t)+1)}^t},\cdots ,W_{{({deg}_{F_t}^{+}(v_t)+{deg}_D^{+}(v_t))}^t}$, respectively. Finally, we consider $h^{\prime }$ assigns l new labels $1^{″\prime },\cdots ,l^{″\prime }$ to the vertices belonging to the remaining sets $W_{{({deg}_{F_t}^{+}(v_t)+{deg}_D^{+}(v_t)+1)}^t},\cdots ,$$W_{{(\overrightarrow{p}(F_t)-1)}^t}$, respectively. We observe that $h^{\prime }$ gives a P-partition of H of cardinality

$$\overrightarrow{p}(D)+{deg}_{F_t}^{+}(v_t)-k+l=\overrightarrow{p}(F_t)=M.$$

All in all, we constructed a P-partition of H of cardinality M. Therefore, $\overrightarrow{p}(D(\mathcal{F}))\le M$ by Claim 1. This completes the proof. □

In view of the results above, since the rooted product graphs are special cases of the hierarchical product of graphs, as defined in [11], it would be interesting to consider the packing partitioning problem in such hierarchical product. Moreover, since those graphs are indeed subgraphs of the Cartesian product, it would be desirable to analyze some possible relationships (monotony for instance) among these three related operations.