# Federated Neural Compression Under Heterogeneous Data

Eric Lei, Hamed Hassani, and Shirin Saeedi Bidokhti  Department of Electrical
and Systems Engineering
University of Pennsylvania, Philadelphia, PA
{elei, hassani<EMAIL_ADDRESS>
###### Abstract

We discuss a federated learned compression problem, where the goal is to learn
a compressor from real-world data which is scattered across clients and may be
statistically heterogeneous, yet share a common underlying representation. We
propose a distributed source model that encompasses both characteristics, and
naturally suggests a compressor architecture that uses analysis and synthesis
transforms shared by clients. Inspired by personalized federated learning
methods, we employ an entropy model that is personalized to each client. This
allows for a global latent space to be learned across clients, and
personalized entropy models that adapt to the clients’ latent distributions.
We show empirically that this strategy outperforms solely local methods, which
indicates that learned compression also benefits from a shared global
representation in statistically heterogeneous federated settings.

##  I Introduction

Traditional learned compression usually takes place in a centralized setting,
where one compression model is learned from data collected from various
sources and stored at a single location. The standard lossy neural compression
models the centralized data as a single source $\bm{x}\sim P_{X}$ supported on
$\mathcal{X}$. Learned compression, under this source assumption, can be set
up through the lens of nonlinear transform coding (NTC) [1]. NTC seeks to find
an analysis transform $g_{a}:\mathcal{X}\rightarrow\mathcal{Y}$ that maps
$\bm{x}$ to a latent variable $\bm{y}$, and a synthesis transform
$g_{s}:\mathcal{Y}\rightarrow\mathcal{X}$ that maps from the latent space back
to the source/reconstruction space. The latent variable $\bm{y}$ is then
quantized to $\hat{\bm{y}}=\lfloor\bm{y}\rceil$ such that each entry is
quantized to the nearest integer, and entropy coded using likelihoods
generated from some entropy model $p_{\hat{\bm{y}}}(\hat{\bm{y}})$. The goal
is to minimize the operational rate-distortion trade-off

$\operatorname{\mathbb{E}}_{\bm{x}}[-\log_{2}p_{\hat{\bm{y}}}({\lfloor
g_{a}(\bm{x})\rceil})]+\lambda\operatorname{\mathbb{E}}_{\bm{x}}[\operatorname{\mathsf{d}}(\bm{x},g_{s}(\lfloor
g_{a}(\bm{x})\rceil)],$ (1)

where $\lambda>0$ controls the trade-off. The transform functions $g_{a}$,
$g_{s}$, as well as the entropy model are all parameterized using neural
networks.

In practice, NTC models are typically trained on aggregated datasets such as
MS-COCO [2] or ImageNet [3], which are collected from many clients into one
location and form the samples from the source $\bm{x}$. Then, a single model
is trained on this source using the objective in (1). This centralized
approach has been successful in a wide variety of applications and modalities
such as image compression [4, 5, 6], compression of channel state information
(CSI) in wireless communications [7, 8], and in audio compression [9].

However, in many cases, a centralized approach is not necessarily feasible or
applicable to the end user’s setting. Rather than already existing in a
central location, the data may be scattered across clients and it may not be
feasible to centrally collect it due to limitations such as privacy
constraints. Moreover, it can be expensive to collect all data at a
centralized location when there are many clients. These challenges motivate
analyzing learned compression from a distributed setup where multiple clients
all wish to learn a compressor for their respective data in a federated
fashion, potentially with the help of a central server.

One immediate challenge that arises is that there are now potentially $n$
different sources, where $n$ is the number of clients. The single source NTC
setup in (1) is, however, formulated for a single source. This parallels a
well-known challenge in federated learning (FL), which is a related problem
where clients wish to jointly learn a classifier or regressor from their data,
where the data across clients are statistically heterogeneous, yet may share
some underlying structure. For example, medical images collected using
different equipment or in different locations may be modeled by different
source distributions; yet, they are all fundamentally the same type of image.
In the context of data compression, a natural question arises: how to model
common structure across statistically heterogeneous sources? Furthermore, how
can this shared structure be leveraged by the clients in order to learn good
lossy compressors for each client?

For the former question, one difference that precludes direct application of
the FL setup is that in FL, the statistical heterogeneity is modeled within
the labels of the data distribution, not the features (e.g., pixel values in
images). Learned compression is, however, an unsupervised task, and has no
labeled data. Thus, all statistical heterogeneity and common structure that
may exist across client data needs to be modeled solely within the features.
In our work, we take these considerations into account by modelling the
clients’ sources as distributions induced by a shared generative function $f$
applied to $n$ independent latent sources. This shared generative function $f$
ensures that all sources share a common feature space.

For the latter question, a naive approach to solve this problem is to try to
learn a single NTC-based compressor, where clients send model updates to the
server at each round, and the server computes the average of the received
models. This approach would extend FedAvg [10] in FL to this federated
compression setting. However, under our source heterogeneity assumption, it is
more natural to learn client-specific compressors that are better tuned to
each client’s source distribution. One client-specific solution is to train a
local model for each client. A challenge this approach faces in practice is
that the number of samples each client has is small relative to the number of
clients. Under our data heterogeneity model, however, there is intrinsic
structure in the feature space defined by the shared function $f$, which can
be leveraged across client data. We thus propose a novel solution with NTC
models: learn globally shared analysis and synthesis transforms, with client-
specific entropy models. This approach allows the shared analysis and
synthesis transforms to try and undo the shared function $f$, extracting the
client-specific latent source, which is then compressed using client-specific
entropy models.

Our contributions are as follows.

  1. 1.

We propose a federated learned compression framework that simultaneously
encompasses statistical heterogeneity and shared intrinsic structure across
clients.

  2. 2.

We propose a novel method to learn client-specific neural compressors that
leverages the shared structure across clients.

  3. 3.

We demonstrate empirically that learning a shared analysis and synthesis
transform followed by locally optimized entropy models performs better than
solely local NTC models.

##  II Related Work

###  II-A Neural Compression

The use of neural networks to design lossy compressors was initiated by
merging quantization with autoencoder architectures [11, 12, 13, 14]. These
methods, under the umbrella of NTC [1], operate by mapping the source to a
latent space and back by using an analysis and synthesis transform
parameterized with neural networks. Uniform quantization and entropy coding
(using an additional learned entropy model) is then performed in the latent
space, which is generally much lower in dimensionality. More recent work
improve upon the entropy modeling to remove additional redundancy in the
latent space. The scale hyperprior [4] transmits side information to generate
different entropy models for each sample, with [5] and [6] building on top of
this via autoregression of the latent variable. In single-image compression,
these methods have shown to outperform recent handcrafted codecs such as HEVC
[15] and VVC [16].

These methods are typically trained on data that has been pre-collected and
stored centrally. One model is typically trained and deployed. In contrast,
our work considers the case where the data resides across distributed clients
such that collecting them centrally is not possible, and designing
architectures to learn good compressors in such a setting.

###  II-B Federated Learning

There have been many recent works discussing federated learning (FL),
especially under client heterogeneity [17, 18, 19, 20]. Most of these works
have been applied in classification or regression settings, where each client
$i$ has its own training data $\bm{x},\bm{y}\sim P_{i}$ and wishes to learn a
good predictor that generalizes well on their respective distribution $P_{i}$.
One popular approach is FedAvg [10], where a single model is sent to clients
to update the model, before the central server averages their updates. Another
approach is FedRep [17], where a global feature extractor is learned on
centralized data, and local client heads are jointly trained which use the
extracted features to predict on local client data. Both methods have been
shown to recover the underlying shared representation across clients in simple
regression settings [21].

One difference in our setup is that learned compression does not assume
labeled data. The assumptions of personalized FL are that heterogeneity
resides in the labels, and hence the natural architecture to arise is a shared
feature extractor followed by a predictor that is personalized. In contrast,
we propose a different notion of heterogeneity with shared structure that
purely resides in the features. We argue that this naturally leads to an
architecture with shared analysis and synthesis transforms followed by
personalized entropy model.

###  II-C Distributed Neural Compression

There have also been recent works in designing distributed neural compression
schemes [22, 23, 24, 25]. These works are inspired by the information-
theoretic results on compression with side information [26, 27], which say
that if one has side information on a source to be compressed, an encoder that
does not observe side information can perform just as well as one that does
(in both cases the decoder observes the side information). However, this is
slightly different from the federated setting. In contrast, we are interested
in learning $n$ point-to-point lossy compressors (i.e., one for each client),
where each compressor does not assume any side information from the other
clients to be available. Rather than exploiting side information (i.e., a
correlated source), we want to exploit underlying structure of the $n$
sources, despite being statistically independent.

##  III Problem Formulation

###  III-A Single-Source Neural Compression

As discussed in the introduction, classical neural compression models the data
as a single source $\bm{x}\sim P_{X}$, and attempts to learn a model that
performs well in terms of rate and distortion defined w.r.t. $\bm{x}$. The
main intuition is that sources such as images have a low-dimensional latent
space which can be extracted by the analysis and synthesis transforms. The
low-dimensional latent representation is modelled probabilistically using a
learned entropy model, which quantizes and entropy codes the latent variable.
A figure describing this setup is shown in Fig. 1.

Figure 1: Single source neural compression.

This method encompasses centralized training, where datasets are aggregated
ahead of time and a single model is trained using the combined data.

###  III-B Federated Compression

In the federated setting, instead of a single, effectively centralized source,
we have $n$ sources $P_{1},\dots,P_{n}$, with $\bm{x}^{(i)}\sim P_{i}$
consisting of the data seen by client $i$. Centralized training corresponds to
aggregating all sources into the single source setup with
$P_{X}=\frac{1}{n}\sum_{i=1}^{n}P_{i}$. Typically, however, since the sources
are heterogeneous across clients, it is better to have client-optimized
models. Thus, the most general federated compression setup consists of $n$
separate compressors, such that each client $i$ has its own analysis and
synthesis transforms $g_{a}^{(i)}$, $g_{s}^{(i)}$, as well as entropy model
$p_{\hat{\bm{y}}}^{(i)}$. Thus, the local federated objective consists of

$\displaystyle\min_{\\{g_{a}^{(i)},g_{s}^{(i)},p_{\hat{\bm{y}}}^{(i)}\\}_{i=1}^{n}}\frac{1}{n}\sum_{i=1}^{n}$
$\displaystyle\bigl{(}\operatorname{\mathbb{E}}_{\bm{x}^{(i)}}[-\log_{2}p_{\hat{\bm{y}}}^{(i)}({\lfloor
g_{a}^{(i)}(\bm{x}^{(i)})\rceil})]$ $\displaystyle+\lambda$
$\displaystyle\operatorname{\mathbb{E}}_{\bm{x}^{(i)}}[\operatorname{\mathsf{d}}(\bm{x}^{(i)},g_{s}^{(i)}(\lfloor
g_{a}^{(i)}(\bm{x}^{(i)})\rceil)]\bigr{)},$ (2)

where the goal is minimize the rate and distortion averaged over the clients.
We call the objective in (2) Local-NTC, whose training algorithm can be found
in Alg 1.

Algorithm 1 Local-NTC

Total iterations $T$, step size $\eta$, rate-distortion tradeoff $\lambda>0$

Initialize $\\{g_{a}^{(i)}\\}_{i=1}^{n},\\{g_{s}^{(i)}\\}_{i=1}^{n}$,
$\\{p_{\hat{\bm{y}}}^{(i)}\\}_{i=1}^{n}$

for $t=1,\dots,T$ do

for each client $i$ do

$(g_{a}^{(i)},g_{s}^{(i)},p_{\hat{\bm{y}}}^{(i)})\leftarrow(g_{a}^{(i)},g_{s}^{(i)},p_{\hat{\bm{y}}}^{(i)})-\eta\nabla_{(g_{a}^{(i)},g_{s}^{(i)},p_{\hat{\bm{y}}}^{(i)})}(R_{n}+\lambda
D_{n})$

end for

end for

Rather than learn a local model for each client, results from federated
learning suggest that heterogeneous data can potentially benefit from first
learning a shared common representation. In the FedRep framework [17], a
common representation is extracted from a shared feature extractor, before
individual client heads are learned to predict from this fixed representation.
The intuition behind these works is the assumption that data heterogeneity
exists primarily in the labels of the dataset, whereas the data samples (e.g.,
covariates or features) have a shared common structure. Learned compression,
on the other hand, is a fully unsupervised task, and so both the heterogeneity
and shared structure need to be modelled within the features.

###  III-C Heterogeneous Source Modelling

As an example, if one wishes to compress similar types of images (e.g.,
medical images) that are collected using different equipment across the
clients, one might expect that these images lie on the same image manifold
despite the image distributions being different across clients.
Mathematically, we can model $P_{1},\dots,P_{n}$ as follows. Let
$\\{\bm{z}^{(i)}\\}_{i=1}^{n}$ be the latent sources of randomness underlying
the images sources, which could represents properties of the images such as
class, orientation, lightning, or style. Then, the sources in the ambient
space which the clients observe are generated as
$\bm{x}^{(i)}=f(\bm{z}^{(i)})$, for some fixed but unknown function $f$, which
models the shared source manifold, but the statistically heterogeneity is
modelled implicitly via the $\bm{z}^{(i)}$’s.

In Local-NTC, the analysis and synthesis transforms at each client attempt to
“undo” this generative function $f$ in order to recover $\bm{z}^{(i)}$ and
model its probability density. However, each client may be data limited, and
thus learning $f$ at every client’s model may be difficult to accomplish.
Instead, in order for each client $i$ to recover the underlying source, it may
be easier to globally learn the function $f$ across clients. The NTC framework
itself naturally possesses an architecture that can naturally support this
heterogeneous source model, where the images across clients share an
underlying latent representation.

###  III-D Sharing Analysis and Synthesis Transforms

The analysis transform can be seen as a feature extractor that extracts a
latent representation (typically of lower dimensionality), which is then
quantized and entropy encoded according to a learned entropy model. One can
thus view the “prediction head” of learned compression as the entropy coding
part of the model. At the decoder side, the decompressed latent variable is
transformed back to the reconstruction using the synthesis transform. Thus, if
one learns a shared analysis and synthesis transform $g_{a},g_{s}$ across
clients, the induced distribution of the latent variables for client $i$ will
be $g_{a}(\bm{x}^{(i)})$. A client-specific entropy model
$p_{\hat{\bm{y}}}^{(i)}$ is then fine-tuned individually to more accurately
model the distribution induced by $g_{a}(\bm{x}^{(i)})$. Similar to federated
learning, we expect this scheme to perform better than solely local training
when the data per-client is small; this helps the analysis and synthesis
transforms learn better feature extractors by leveraging all the data across
clients. We call this setting Fed-NTC, where the objective is

$\displaystyle\min_{g_{a},g_{s},\\{p_{\hat{\bm{y}}}^{(i)}\\}_{i=1}^{n}}\frac{1}{n}\sum_{i=1}^{n}$
$\displaystyle\bigl{(}\operatorname{\mathbb{E}}_{\bm{x}^{(i)}}[-\log_{2}p_{\hat{\bm{y}}}^{(i)}({\lfloor
g_{a}(\bm{x}^{(i)})\rceil})]$ $\displaystyle+\lambda$
$\displaystyle\operatorname{\mathbb{E}}_{\bm{x}^{(i)}}[\operatorname{\mathsf{d}}(\bm{x}^{(i)},g_{s}(\lfloor
g_{a}(\bm{x}^{(i)})\rceil)]\bigr{)},$ (3)

which jointly optimizes the client-averaged rate and distortion $R_{n}+\lambda
D_{n}$, where $R_{n}$ and $D_{n}$ are defined as

$R_{n}:=\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{\bm{x}^{(i)}}[-\log_{2}p_{\hat{\bm{y}}}^{(i)}({\lfloor
g_{a}(\bm{x}^{(i)})\rceil})],$ (4)
$D_{n}:=\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{\bm{x}^{(i)}}[\operatorname{\mathsf{d}}(\bm{x}^{(i)},g_{s}(\lfloor
g_{a}(\bm{x}^{(i)})\rceil)].$ (5)

Fig. 2 describes the training framework. To optimize (3), one can alternate
global updates, which are coordinated through the use of a server as shown in
Fig. 2, with local entropy model updates. The full algorithm is shown in Alg.
2.

Figure 2: Federated neural compression under Fed-NTC framework. Analysis and
synthesis transforms are learned globally through a central server, whereas
the entropy models are learned per-client. Algorithm 2 Fed-NTC

Participation rate $r$, communication rounds $T$, entropy model updates
$T_{p}$, transform updates $T_{g}$, step size $\eta$, rate-distortion tradeoff
$\lambda>0$

Initialize $g_{a},g_{s}$, $\\{p_{\hat{\bm{y}}}^{(i)}\\}_{i=1}^{n}$

for $t=1,\dots,T$ do

Server sends $g_{a},g_{s}$ to random fraction $r$ of clients $I_{r}$

for $T_{p}$ iterations do

$p_{\hat{\bm{y}}}^{(i)}\leftarrow
p_{\hat{\bm{y}}}^{(i)}-\eta\nabla_{p_{\hat{\bm{y}}}^{(i)}}(R_{n}+\lambda
D_{n}),\quad\forall i\in I_{r}$

end for

Initialize $(g_{a}^{(i)},g_{s}^{(i)})\leftarrow(g_{a},g_{s}),\forall i\in
I_{r}$

for $T_{g}$ iterations do

$(g_{a}^{(i)},g_{s}^{(i)})\leftarrow(g_{a}^{(i)},g_{s}^{(i)})-\eta\nabla_{(g_{a}^{(i)},g_{s}^{(i)})}(R_{n}+\lambda
D_{n})$

end for

Each client $i$ sends $(g_{a}^{(i)},g_{s}^{(i)})$ back to server

$(g_{a},g_{s})\leftarrow\frac{1}{rn}\sum_{i\in
I_{r}}(g_{a}^{(i)},g_{s}^{(i)})$

end for

###  III-E Rate-Distortion Function For Heterogeneous Sources

In this section, we explain why sharing analysis and synthesis transforms is
principled, from a rate-distortion point of view. In general, the rate-
distortion function of $n$ independent (but not necessarily identical) sources
$\bm{x}^{(i)}\sim P_{i}$ is achievable using a locally optimal code for each
source, with an appropriate rate allocation across the $n$ sources. As such,
the optimal trade-off between client-averaged rate and distortion
$R^{\mathsf{fed}}(D)$ is given by [28, Sec. 10.3.3]

$R^{\mathsf{fed}}(D)=\min_{D_{1},\dots,D_{n}:\frac{1}{n}\sum_{i=1}^{n}D_{i}\leq
D}\frac{1}{n}\sum_{i=1}^{n}R_{i}(D_{i}),$ (6)

where $R_{i}(D)$ is the rate-distortion function of $P_{i}$. This result
appears to suggest that to obtain the best rate-distortion trade-off, it
suffices to should learn $n$ separate compressors, one for each client, which
is what Local-NTC does. However, under our proposed heterogeneous source model
described in Sec. III-C, codes that share a global transform can also achieve
$R^{\mathsf{fed}}(D)$ using the following structure. Setting $g_{a}=f^{-1}$
and $g_{s}=f$, first transform $\bm{x}^{(i)}$ to $\bm{z}^{(i)}$, which is
compressed using an optimal code with respect to distortion function

$\operatorname{\mathsf{d}}_{z}(\bm{z}^{(i)},\hat{\bm{z}}^{(i)}):=\operatorname{\mathsf{d}}(f(\bm{z}^{(i)}),f(\hat{\bm{z}}^{(i)})).$
(7)

The compressed version of $\bm{z}^{(i)}$ is transformed back using $f$. Thus,
assuming that $\bm{z}^{(i)}$ can be optimally compressed, both Local-NTC and
Fed-NTC possess the architectures to perform optimal compression using this
above scheme. However, in Local-NTC, each user’s pair of transforms will need
to learn $f^{-1}$ and $f$ individually, whereas in Fed-NTC, $f$ only needs to
be learned for a single set of transforms at the global level, which should
benefit learning-based compressors, especially when samples are limited. An
algorithmic analysis of Fed-NTC is left for future work.

##  IV Experiments

We first discuss how we set up the experiments in order to introduce
heterogeneity in the data, followed by their results.

###  IV-A Experimental Setup

####  IV-A1 Datasets

To experimentally test the Fed-NTC framework, we test a federated setup on
image compression of SVHN, and CIFAR10 datasets, which are all $32\times 32$
RGB image datasets. While generally used for classification purposes, we use
their class identities to introduce data heterogeneity across the clients.
SVHN and CIFAR10 are both 10-class datasets. We assign $S$ classes to each
client, on average, by using the non-i.i.d. data partitioning method detailed
in [10]. We then vary $S$ in order to vary the heterogeneity across clients,
where $S\in\\{2,5\\}$. The number of training samples per user is fixed at
$N/n$, where $N$ is the total number of training samples. This way of
introducing heterogeneity can be viewed as the latent source $\bm{z}^{(i)}$
representing features of the subset of classes; for example, different poses
and styles of the class object within the image frame. The generative mapping
$f$ then projects these features to the image manifold.

####  IV-A2 Compression Models

For the compression models, we use the NTC methods detailed in [1], with a
factorized prior for $p_{\hat{\bm{y}}}$, which models each entry of
$p_{\hat{\bm{y}}}$ independently using a single-variable density model
parameterized by a neural network. In practice, all spatial elements along
each channel dimension are modeled by the same density model in order to
maintain translation-invariance across the entire model [4]. We add uniform
noise to the $g_{a}(\bm{x})$ to serve as a proxy during training, with hard
quantization and entropy coding during evaluation of the models.

####  IV-A3 Federated Setup

For the federated setup, we use a total of $n=100$ clients in all image
compression experiments. For the baseline model (Local-NTC), which consists of
each client having its own model, each client trains its model on its own
local data, e.g. in Alg. 1, with no communication among the clients. For the
proposed Fed-NTC method, we use a participation rate of $r=0.1$ in Alg. 2 and
a total of 100 rounds of communication. For evaluation, the number of bits
needed to compress the hard-quantized latents, and the distortion are measured
and averaged for the final 10 rounds of communications.

###  IV-B Results

(a) 2 classes per client.

(b) 5 classes per client.

Figure 3: SVHN with 100 clients.

(a) 2 classes per client.

(b) 5 classes per client.

Figure 4: CIFAR10 with 100 clients.

(a) 2 classes per client.

(b) 5 classes per client.

Figure 5: SVHN with 100 clients, compared with a single global NTC model
trained under FedAvg.

(a) 2 classes per client.

(b) 5 classes per client.

Figure 6: CIFAR10 with 100 clients, compared with a single global NTC model
trained under FedAvg.

In Figs. 3 and 4, we plot the comparisons of Fed-NTC with Local-NTC for
CIFAR10 and SVHN, respectively. We observe that in almost all settings, Fed-
NTC outperforms Local-NTC models. This indicates that learning a shared
representation is able to compress the data across clients better at a variety
of different levels of heterogeneity, and that shared generative function is a
plausible model for the heterogeneous data with shared structure. The Fed-NTC
models are able to recover the global functon $f$ by leveraging the data
across clients.

We additionally compare Fed-NTC with a model that shared a single global model
across all users. This model, trained under the FedAvg scheme [10], alternates
between 10 local updates for each client, before sending back to the server
which averages all models. As shown in Figs. 5 and 6, such a model performs
significantly worse than Fed-NTC and even local training, indicating that a
single global model struggles with client heterogeneity in learned
compression. We noted no significant difference if the number of local updates
was reduced in an effort to reduce client drift.

Finally, we run an additional experiment which varies the number of users $n$
(and thus the number of samples allotted to each user). In previous figures,
we set $n=100$. In Fig. 7, we reduce the number of users to $n=50$ and $n=20$.
We observe that at $n=50$ there is no significant change compared to $n=100$,
but at $n=20$ both Fed-NTC and Local-NTC improve in terms of rate-distortion
performance.

##  V Conclusion

We propose a federated framework for learned compression, where the data
across clients may be heterogeneous. We propose a model for such data that has
shared structure in the form of a common generative function. This model
suggests that in compression, one should first extract a common latent space
before client-specific entropy modelling takes place. Experimental results
confirm that this assumption is true across a broad class of settings and this
scheme is superior to solely local models. Potential avenues for future work
include analyzing privacy aspects and algorithmic analysis of different
federated schemes.

(a) 2 classes per client.

(b) 5 classes per client.

Figure 7: CIFAR10, varying number of users.

## References

  * [1] J. Ballé, P. A. Chou, D. Minnen, S. Singh, N. Johnston, E. Agustsson, S. J. Hwang, and G. Toderici, “Nonlinear transform coding,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 15, no. 2, pp. 339–353, 2021.
  * [2] T.-Y. Lin, M. Maire, S. Belongie, J. Hays, P. Perona, D. Ramanan, P. Dollár, and C. L. Zitnick, “Microsoft coco: Common objects in context,” in _Computer Vision–ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V 13_. Springer, 2014, pp. 740–755.
  * [3] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in _2009 IEEE Conference on Computer Vision and Pattern Recognition_ , 2009, pp. 248–255.
  * [4] J. Ballé, D. Minnen, S. Singh, S. J. Hwang, and N. Johnston, “Variational image compression with a scale hyperprior,” _arXiv preprint arXiv:1802.01436_ , 2018.
  * [5] D. Minnen, J. Ballé, and G. D. Toderici, “Joint autoregressive and hierarchical priors for learned image compression,” _Advances in neural information processing systems_ , vol. 31, 2018.
  * [6] D. Minnen and S. Singh, “Channel-wise autoregressive entropy models for learned image compression,” in _2020 IEEE International Conference on Image Processing (ICIP)_. IEEE, 2020, pp. 3339–3343.
  * [7] Q. Yang, M. B. Mashhadi, and D. Gündüz, “Deep convolutional compression for massive mimo csi feedback,” in _2019 IEEE 29th international workshop on machine learning for signal processing (MLSP)_. IEEE, 2019, pp. 1–6.
  * [8] S. Ravula and S. Jain, “Deep autoencoder-based massive mimo csi feedback with quantization and entropy coding,” in _2021 IEEE Global Communications Conference (GLOBECOM)_ , 2021, pp. 1–6.
  * [9] A. Défossez, J. Copet, G. Synnaeve, and Y. Adi, “High fidelity neural audio compression,” _arXiv preprint arXiv:2210.13438_ , 2022.
  * [10] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Artificial intelligence and statistics_. PMLR, 2017, pp. 1273–1282.
  * [11] G. Toderici, S. M. O’Malley, S. J. Hwang, D. Vincent, D. Minnen, S. Baluja, M. Covell, and R. Sukthankar, “Variable rate image compression with recurrent neural networks,” in _4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings_ , Y. Bengio and Y. LeCun, Eds., 2016. [Online]. Available: http://arxiv.org/abs/1511.06085
  * [12] J. Ballé, V. Laparra, and E. P. Simoncelli, “End-to-end optimized image compression,” in _International Conference on Learning Representations_ , 2017. [Online]. Available: https://openreview.net/forum?id=rJxdQ3jeg
  * [13] L. Theis, W. Shi, A. Cunningham, and F. Huszár, “Lossy image compression with compressive autoencoders,” in _International Conference on Learning Representations_ , 2017. [Online]. Available: https://openreview.net/forum?id=rJiNwv9gg
  * [14] E. Agustsson, F. Mentzer, M. Tschannen, L. Cavigelli, R. Timofte, L. Benini, and L. V. Gool, “Soft-to-hard vector quantization for end-to-end learning compressible representations,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [15] G. J. Sullivan, J.-R. Ohm, W.-J. Han, and T. Wiegand, “Overview of the high efficiency video coding (hevc) standard,” _IEEE Transactions on Circuits and Systems for Video Technology_ , vol. 22, no. 12, pp. 1649–1668, 2012\.
  * [16] B. Bross, Y.-K. Wang, Y. Ye, S. Liu, J. Chen, G. J. Sullivan, and J.-R. Ohm, “Overview of the versatile video coding (vvc) standard and its applications,” _IEEE Transactions on Circuits and Systems for Video Technology_ , vol. 31, no. 10, pp. 3736–3764, 2021.
  * [17] L. Collins, H. Hassani, A. Mokhtari, and S. Shakkottai, “Exploiting shared representations for personalized federated learning,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 2089–2099.
  * [18] A. Mitra, R. Jaafar, G. J. Pappas, and H. Hassani, “Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 14 606–14 619, 2021.
  * [19] S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. T. Suresh, “Scaffold: Stochastic controlled averaging for federated learning,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 5132–5143.
  * [20] A. Reisizadeh, I. Tziotis, H. Hassani, A. Mokhtari, and R. Pedarsani, “Straggler-resilient federated learning: Leveraging the interplay between statistical accuracy and system heterogeneity,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 3, no. 2, pp. 197–205, 2022.
  * [21] L. Collins, H. Hassani, A. Mokhtari, and S. Shakkottai, “Fedavg with fine tuning: Local updates lead to representation learning,” _arXiv preprint arXiv:2205.13692_ , 2022.
  * [22] M. B. Mashhadi, Q. Yang, and D. Gündüz, “Distributed deep convolutional compression for massive mimo csi feedback,” _IEEE Transactions on Wireless Communications_ , vol. 20, no. 4, pp. 2621–2633, 2021.
  * [23] N. Mital, E. Özyılkan, A. Garjani, and D. Gündüz, “Neural distributed image compression using common information,” in _2022 Data Compression Conference (DCC)_. IEEE, 2022, pp. 182–191.
  * [24] N. Mital, E. Özyilkan, A. Garjani, and D. Gündüz, “Neural distributed image compression with cross-attention feature alignment,” in _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , 2023, pp. 2498–2507.
  * [25] J. Whang, A. Acharya, H. Kim, and A. G. Dimakis, “Neural distributed source coding,” _arXiv preprint arXiv:2106.02797_ , 2021.
  * [26] D. Slepian and J. Wolf, “Noiseless coding of correlated information sources,” _IEEE Transactions on Information Theory_ , vol. 19, no. 4, pp. 471–480, 1973\.
  * [27] A. Wyner and J. Ziv, “The rate-distortion function for source coding with side information at the decoder,” _IEEE Transactions on Information Theory_ , vol. 22, no. 1, pp. 1–10, 1976.
  * [28] T. M. Cover and J. A. Thomas, _Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing)_. USA: Wiley-Interscience, 2006.

## Acknowledgments

The work of Eric Lei was supported by a NSF Graduate Research Fellowship. The
work of Shirin Saeedi Bidokhti was supported by NSF award 1910594 and an NSF
CAREER award 2047482. The work of Hamed Hassani was supported by NSF award
CIF-1943064. This work was also partially supported by the AI Institute for
Learning-Enabled Optimization at Scale (TILOS), NSF award CCF-2112665.


# On $k$-(total) limited packing in graphs

Azam Sadat Ahmadi and Nasrin Soltankhah
Department of Mathematics, Faculty of Mathematical Sciences, Alzahra
University,
Tehran, Iran
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
Corresponding author

###### Abstract

A set $B\subseteq V(G)$ is called a $k$-total limited packing set in a graph
$G$ if $|B\cap N(v)|\leq k$ for any vertex $v\in V(G)$. The $k$-total limited
packing number $L_{k,t}(G)$ is the maximum cardinality of a $k$-total limited
packing set in $G$. Here, we give some results on the $k$-total limited
packing number of graphs emphasizing trees, especially when $k=2$. We also
study the $2$-(total) limited packing number of some product graphs.

A $k$-limited packing partition ($k$LPP) of graph $G$ is a partition of $V(G)$
into $k$-limited packing sets. The minimum cardinality of a $k$LPP is called
the $k$LPP number of $G$ and is denoted by $\chi_{\times k}(G)$, and we obtain
some results for this parameter.

2010 Mathematical Subject Classification: 05C05, 05C69, 05C76
Keywords: limited packing, $k$-limited packing partition number, graph
products.

##  1 Introduction and preliminaries

In this work, we consider $G=\big{(}V(G),E(G)\big{)}$ as a finite simple
graph. $N_{G}(v)$ and $N_{G}[v]=N_{G}(v)\cup\\{v\\}$ are used to refer to the
open neighborhood and closed neighborhood of a vertex $v\in V(G)$,
respectively. The minimum and maximum degrees of a graph $G$ are denoted by
$\delta(G)$ and $\Delta(G)$, respectively. We refer to [12] as a source for
terminology and notation that is not explicitly defined here.

$G^{-}$ indicates the graph obtained from $G$ by removing its isolated
vertices. By $G[S]$, we mean the subgraph induced by the subset $S$ of
vertices in $G$.

A set of vertices $S\subseteq V(G)$ is called a dominating set (DS) in $G$ if
every vertex not in $S$ is adjacent to at least one vertex in $S$. The
domination number of $G$, denoted $\gamma(G)$, is the smallest number of
vertices in a dominating set of $G$. A set $S\subseteq V(G)$ is a total
dominating set (TDS) in the graph $G$ if every vertex in $V(G)$ is adjacent to
a vertex of $S$. The total domination number of $G$, denoted $\gamma_{t}(G)$,
is the smallest number of vertices in a total dominating set of $G$.

A set of vertices $S\subseteq V(G)$ with $\delta(G)\geq k-1$ is said to be a
$k$-tuple dominating set ($k$TD set) in $G$ provided that for every $v\in
V(G)$, we have $|N[v]\cap S|\geq k$ . The $k$-tuple domination number
$\gamma_{\times k}(G)$ of graph $G$ is the number of vertices in a smallest
$k$TD set in $G$. A $k$-tuple domatic partition ($k$TD partition) of a graph
$G$ is a partition of the vertices of $G$ into $k$TD sets. The largest number
of sets that can be obtained from a vertex partition of $G$ into $k$TD sets is
called the $k$-tuple domatic number and is denoted by $d_{\times k}(G)$.
Notice that when $k=1$, $S$ and $\gamma_{\times 1}(G)$ are the usual
dominating set and domination number $\gamma(G)$, respectively. Additionally,
$d_{\times 1}(G)=d(G)$ refers to the well-studied domatic number (see [3]).

A vertex subset $B$ of a graph $G$ is called a packing (resp. an open packing)
provided that $|B\cap N[v]|\leq 1$ (resp. $|B\cap N(v)|\leq 1$) for each
vertex $v\in V(G)$. The packing number $\rho(G)$ and open packing number
$\rho_{o}(G)$ are defined as the maximum cardinality of a packing set and an
open packing set, respectively. To obtain additional information on these
concepts, the reader can refer to [6] and [7].

In $2010$, the concept of limited packing (LP) in graphs was introduced by
Gallant et al. [5]. A $k$-limited packing ($k$LP) in a graph $G$ is a set
$B\subseteq V(G)$ such that for each vertex $v$ of $V(G)$, the cardinality of
the intersection of $B$ and $N[v]$ is at most $k$. The maximum cardinality of
a $k$-limited packing set in G is called the $k$-limited packing number
$L_{k}(G)$. They also presented some real-world applications of this concept
in network security, market situation, NIMBY and codes. This topic was next
investigated in numerous papers, such as references [2], [4] and [11].
Similarly, a $k$-total limited packing ($k$TLP) in $G$ is a set $B\subseteq
V(G)$ such that for each vertex $v$ of $V(G)$, the cardinality of the
intersection of $B$ and $N(v)$ is at most $k$. The maximum cardinality of a
$k$-total limited packing set in G is called the $k$-total limited packing
number $L_{k,t}(G)$. This topic was initially studied in [8], and some
theoretical applications of it were given in [1, 9]. It is worth noting that
the latter two concepts are identical to packing and open packing when $k$
equals $1$. Notice that a $k$LP set is a $k$TLP set, too.

For the cartesian product of graphs $G$ and $H$, denoted $G\square H$, and the
direct product of graphs $G$ and $H$, denoted $G\times H$, the vertex set of
the product is $V(G)\times V(H)$. Their edge sets are defined as follows. In
$G\square H$, two vertices are adjacent if they are adjacent in one coordinate
and equal in the other. In $G\times H$ two vertices are adjacent if they are
adjacent in both coordinates.

Suppose that $G$ is a labeled graph on $n$ vertices, and $\mathcal{H}$ is a
sequence of $n$ rooted graphs $H_{1},H_{2},\cdots,H_{n}$. If we identify the
$i^{th}$ vertex of $G$ with the root of $H_{i}$, we obtain a new graph called
the rooted product graph. This graph is denoted by $G(\mathcal{H})$. We here
focus on the special case of rooted product graphs for which $\mathcal{H}$
consists of $n$ isomorphic rooted graph. Assume that $v$ is the root vertex of
$H$, we define the rooted product graph $G\circ_{v}H=(V,E)$, such that
$V=V(G)\times V(H)$ and

$E=\displaystyle\bigcup_{i=1}^{n}\big{\\{}(g_{i},h)(g_{i},h^{\prime}):hh^{\prime}\in
E(H)\big{\\}}\cup\big{\\{}(g_{i},v)(g_{j},v):g_{i}g_{j}\in E(G)\big{\\}}.$

For $g\in V(G)$, $h\in V(H)$ and $\ast\in\\{\square,\times,\circ_{v}\\}$, we
call $G^{h}=\\{(g,h)\in V(G\ast H)|g\in V(G)\\}$ a $G$-layer through $h$, and
${}^{g}\\!H=\\{(g,h)\in V(G\ast H)|h\in V(H)\\}$ an $H$-layer through $g$ in
$G\ast H$.

Notice that the subgraphs induced by the $H$-layers (resp. the $G$-layers) of
$G\circ_{v}H$ (or $G\square H$) are isomorphic to $H$ (resp. to $G$). However,
there are no edges between the vertices of $G^{h}$ and the vertices of
${}^{g}\\!H$ in direct product $G\times H$.

A $k$-limited packing partition ($k$LPP) of a graph $G$ is a partition of the
vertices of $G$ into $k$LP sets. The smallest number of sets that can be
obtained from a vertex partition of $G$ into $k$LP sets is called the
$k$-limited packing partition number ($k$LPP number) and is denoted by
$\chi_{\times k}(G)$. This concept can also be considered as the dual of $k$TD
partition problem. Our main focus for $k$TLP sets is on $k=2$. This is because
for larger values of $k$, we lose some significant families of graphs (for
instance, $\gamma_{\times k}$ and $d_{\times k}$ cannot be defined for trees
when $k\geq 3$) or we encounter trivial problems (for instance, $L_{\times
k}(G)=|V(G)|$ and $\chi_{\times k}(G)=1$ if $k\geq\Delta(G)+1$). On the other
side, many results for $k\in\\{1,2\\}$ may be generalized to the general case
$k$. Inaddition, Stronger results may be obtained for small values of $k$.

Here, we first discuss $k$TLP, especially when $k=2$, and give several sharp
bounds for it. Then, we improve some of these inequalities for trees. In
Section $3$, we bound $L_{2}$ and $L_{2,t}$ for the cartesian product, direct
product and rooted product graphs . In Section $4$, we give a lower bound for
$\chi_{\times k}$, and determine the values of $\chi_{\times 2}$ for the
corona product. For the sake of convenience, for any graph $G$ by an
$\eta(G)$-set with $\eta\in\\{L_{k},\gamma_{t},\rho,\rho_{o},L_{k,t}\\}$ we
mean a $k$LP set, TD set, packing set, open packing set and $k$TLP set in $G$
of cardinality $\eta(G)$, respectively.

##  2 Results on $k$-total limited packing

If $G$ is a graph of order $n$ and $k\geq n-1$, then $L_{k,t}(G)=n$. Note that
$k\geq\Delta(G)$ is a weaker condition than the previous one. Therefore, we
only need to compute the $k$TLP number for those graphs G such that
$k<\Delta(G)$.

If $B\subseteq V(G)$ and $|B|=k$, then $|B\cap N(v)|\leq k$ for each vertex
$v$ of $V(G)$. So, $k\leq L_{k,t}(G)\leq n$.
We give some upper bounds for the $k$TLP number of a graph in the following.

######  Theorem 2.1.

Let $G$ be a graph of order $n\geq 2$ with degree sequence
$d_{1},d_{2},\cdots,d_{n}$ such that $d_{1}\leq d_{2}\leq\cdots\leq d_{n}$.
Then

$L_{k,t}(G)\leq max~{}\\{t|d_{1}+d_{2}+\cdots+d_{t}\leq kn\\},$

and this bound is sharp.

###### Proof.

Let $\mathcal{B}=\\{v_{1},v_{2},\cdots,v_{|\mathcal{B}|}\\}$ be an
$L_{k,t}(G)$-set. Then

$d_{1}+d_{2}+\cdots+d_{|\mathcal{B}|}\leq
deg(v_{1})+deg(v_{2})+\cdots+deg(v_{|\mathcal{B}|})\leq
k|\mathcal{B}|+k(n-|\mathcal{B}|).$

So $d_{1}+d_{2}+\cdots+d_{|\mathcal{B}|}\leq kn$. Therefore,
$L_{k,t}(G)\in\\{t|d_{1}+d_{2}+\cdots+d_{t}\leq kn\\}$.

The sharpness of this bound can be seen as follows. Suppose that $G$ is a
complete graph of order at least $k+2$. Then, it is easy to see that
$L_{k,t}(G)=k$. On the other hand, $k=L_{k,t}(G)\leq max~{}\\{t|t(n-1)\leq
kn\\}=k$. ∎

######  Lemma 2.2.

If $G$ is a graph of order $n$, then $L_{k,t}(G)\leq n+k-\Delta(G)$.

###### Proof.

Assume that $w$ is a vertex of maximum degree in $G$. If $k\geq\Delta(G)$,
then it is clear that $V(G)$ is a $k$TLP set of $G$. So, $L_{k,t}(G)=n\leq
n+k-\Delta(G)$. Thus, we assume that $k<\Delta(G)$. Let $S$ be an
$L_{k,t}(G)$-set. Since $|N(w)\cap S|\leq k$, there is at least $\Delta(G)-k$
vertices in $N(w)\backslash S$. Hence, $|\overline{S}|\geq\Delta(G)-k$.
Therefore, we have $L_{k,t}(G)=|S|=n-|\overline{S}|\leq n+k-\Delta(G)$. ∎

We define the family $\Omega$ consisting of all graphs $G$ constructed as
follows.
Suppose that $G$ is a graph of order $n$ such that $V(G)=A\cup B$ has the
following conditions:

  * (i)

$|A\cap B|=3$,

  * (ii)

$G[A]$ has a spanning star, and each component of $G[B]$ is a path or a cycle,

  * (iii)

for every vertex $v\in\overline{B}$, we have $|N(v)\cap B|\leq 2$ .

Figure 1 depicts a representative member of $\Omega$.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$ Figure 1: A graph
$H\in\Omega$ with $A=\\{v_{1},v_{2},v_{3},v_{4},v_{5}\\}$ and
$B=\\{v_{1},v_{3},v_{5},v_{6},v_{7},v_{8}\\}$.

The next theorem shows that $\Omega$ is the set of all graphs $G$ of order $n$
satisfying $L_{2,t}(G)=n+2-\Delta(G)$.

######  Theorem 2.3.

If $G$ is a graph of order $n$, then $L_{2,t}(G)\leq n+2-\Delta(G)$.
Furthermore, $L_{2,t}(G)=n+2-\Delta(G)$ if and only if $G\in\Omega$.

###### Proof.

Suppose that $S$ is an $L_{2,t}(G)$-set, and $w$ is a vertex of maximum degree
in $G$. Notice that each component of $G[S]$ is a path or a cycle, and we have
$L_{2,t}(G)=|S|=n-|\overline{S}|\leq n+2-\Delta(G)$ by Lemma 2.2.

If $L_{2,t}(G)=n+2-\Delta(G)$, then $|\overline{S}|=\Delta(G)-2$,
$\big{(}V(G)\backslash N[w]\big{)}\subseteq S$ and $|N[w]\cap S|=3$. Based on
the above argument, we have $G\in\Omega$ with $N[w]=A$ and $S=B$.

Let now $G\in\Omega$, then it suffices to prove that $L_{2,t}(G)\geq
n+2-\Delta(G)$. Assume now that $A\cap B=\\{u_{1},u_{2},u_{3}\\}$ and
$|A|=a+1$, where $w$ is a vertex of degree $a$ in $G[A]$. We claim that
$\Delta(G)=a$. Each vertex $v\in B$ in $G[B]$ is at most of degree two. So,
each of the vertices $u_{1},u_{2}$ and $u_{3}$ is adjacent to at most two
vertices in $B$. On the other hand, each of $u_{1},u_{2},u_{3}$ is adjacent to
at most $a-2$ vertices in $A\backslash\\{u_{1},u_{2},u_{3}\\}$. Thus,
deg$(u_{1})\leq a$, deg$(u_{2})\leq a$ and deg$(u_{3})\leq a$. For each vertex
$v\in A\backslash\\{u_{1},u_{2},u_{3}\\}$, $v$ is adjacent to at most $a-3$
vertices in $A\backslash\\{u_{1},u_{2},u_{3},v\\}$ and to at most two vertices
in $B$. So deg$(v)\leq a-1$ for every $v\in
A\backslash\\{u_{1},u_{2},u_{3}\\}$. For each vertex $v^{\prime}\in
B\backslash\\{u_{1},u_{2},u_{3}\\}$, $v^{\prime}$ is adjacent to at most $a-2$
vertices in $A\backslash\\{u_{1},u_{2},u_{3}\\}$ and to at most two vertices
in $B$. Thus, deg$(v^{\prime})\leq a$ for every $v^{\prime}\in
B\backslash\\{u_{1},u_{2},u_{3}\\}$. Thus, $\Delta(G)\leq a$. But deg$(w)\geq
a$, which implies that $\Delta(G)=a$. Note that $B$ is a $2$TLP set of $G$
with $|B|=n-|A|+3=n+2-\Delta(G)$. Therefore, we have $L_{2,t}(G)\geq
n+2-\Delta(G)$. ∎

######  Corollary 2.4.

Let $G$ be an $r$-regular graph of order $n$ such that $L_{k,t}(G)=n+k-r$ for
$k\leq r-1$. Then, we have $r\geq\frac{n+1}{2}$.

###### Proof.

If $r=n-1$, then $G$ is a complete graph with $L_{k,t}(G)=k$ for $1\leq k\leq
n-2$. So, let $r\leq n-2$. Now assume that $w\in V(G)$ and that $S$ is an
$L_{k,t}(G)$-set with $|S|=n+k-r$. Since $|N(w)\cap S|\leq k$, it follows that
$|N(w)\cap\overline{S}|\geq r-k$ . Obviously, $|\overline{S}|=n-|S|=r-k$.
Thus, there are exactly $r-k$ vertices, namely $v_{1},v_{2},\cdots,v_{r-k}$,
in $N(w)\cap\overline{S}$. Moreover,
$\overline{S}=\\{v_{1},v_{2},\cdots,v_{r-k}\\}$. Let $U=V(G)\backslash N(w)$,
clearly $U\subseteq S$, and $U\neq\emptyset$ since $r\leq n-2$. If $u\in U$,
then $|N(u)\cap S|\leq k$. So, any vertex $u\in U$ is adjacent to all vertices
in $\overline{S}$, i.e. every vertex $v_{i}\in\overline{S}$ is adjacent to all
$n-r$ vertices in $U$. Note that $v_{i}$ has at least one neighbor in $N[w]$,
and deg$(v_{i})=r$. Therefore, $n-r+1\leq r$ and we get $r\geq\frac{n+1}{2}$.
∎

For any tree $T$ with order $n\geq 3$, $\delta^{\prime}(T)$ denotes the
minimum degree of $T$ among all non-leaf vertices.

######  Theorem 2.5.

Let $T$ be a tree of order $n\geq 3$ for which $\delta^{\prime}(T)\geq c$, and
let $c\geq 4$ be a positive integer. Then, we have
$L_{2,t}(T)\leq\frac{c-2}{c-1}n-c+4$.

###### Proof.

We prove this theorem by induction on the order of tree $T$. Since
$\delta^{\prime}(T)\geq c$, we have $n\geq c+1$. If
$n\in\\{c+1,c+2,\cdots,2c-1\\}$, then
$T\in\\{K_{1,c},K_{1,c+1},\cdots,K_{1,2c-2}\\}$, respectively. Hence,
$L_{2,t}(T)=3\leq\frac{c-2}{c-1}n-c+4$. Assume that for all tree $T^{\prime}$
of order $n^{\prime}<n$ with $\delta^{\prime}(T^{\prime})\geq c$, we have
$L_{2,t}(T^{\prime})\leq\frac{c-2}{c-1}n^{\prime}-c+4$. Now let $T$ be a tree
of order $n\geq 2c$ such that $\delta^{\prime}(T)\geq c$ and let $S$ be an
$L_{2,t}(T)$-set. We root $T$ at $r$, and suppose $v^{\prime}$ is a leaf of
$T$ at the furthest distance from $r$, and $v^{\prime\prime}$ is the parent of
$v^{\prime}$. Assume that $L$ is the set of all leaves in
$N(v^{\prime\prime})$. Since $v^{\prime\prime}$ is adjacent to at least $c-1$
leaves, it follows that $|L|\geq c-1$. Suppose that $T^{\prime\prime}$ be
obtained from $T$ by deleting all the vertices of $L$. By the induction
hypothesis, we have
$L_{2,t}(T^{\prime\prime})\leq\frac{c-2}{c-1}|V(T^{\prime\prime})|-c+4\leq\frac{c-2}{c-1}(n-(c-1))-c+4=\frac{c-2}{c-1}n-2c+6$.

On the other hand, $|L\cap S|\leq|N(v^{\prime\prime})\cap S|\leq 2$.
Therefore, we get $L_{2,t}(T)\leq
L_{2,t}(T^{\prime\prime})+2\leq\frac{c-2}{c-1}n-2c+8\leq\frac{c-2}{c-1}n-c+4$.
∎

######  Theorem 2.6.

If $G$ is a graph, then for any edge $e\in E(G)$,

$L_{k,t}(G)\leq L_{k,t}(G-e)\leq L_{k,t}(G)+2.$

Furthermore, these bounds are sharp.

###### Proof.

Any $k$TLP set of $G$ is also a $k$TLP set of $G-e$, so $L_{k,t}(G)\leq
L_{k,t}(G-e)$. Moreover, if $C$ is a cycle on $n$ vertices, then
$L_{2,t}(C)=L_{2,t}(C-e)$ for every edge $e\in E(C)$.

Suppose now that $B$ is an $L_{k,t}(G-e)$-set and $e=uv$. If $u,v\in B$, then
$B-\\{u,v\\}$ is a $k$TLP set of $G$ ,and hence $L_{k,t}(G)\geq|B|-2$. If
$u\in B$ and $v\notin B$, then $B-\\{u\\}$ is a $k$TLP set of $G$, and
$L_{k,t}(G)\geq|B|-1$. If $u,v\notin B$, then $B$ is a $k$TLP set of $G$, and
we have $L_{k,t}(G)\geq|B|$. Therefore, $L_{k,t}(G-e)\leq L_{k,t}(G)+2$.

Let $G$ be a double star $ST(x,y)$, which is the graph obtained by joining the
centers of two stars $K_{1,x}$ and $K_{1,y}$ with an edge, such that $x,y\geq
k+1$. Assume that the center of stars are $u$ and $v$, respectively. Then,
$L_{k,t}(G-e)=L_{k,t}(G)+2$ for $e=uv$. ∎

######  Proposition 2.7.

Let $G$ be a graph without isolated vertices such that $\Delta(G)\geq 2$, then

$\rho_{o}(G)+1\leq
L_{2,t}(G)\leq\frac{{\Delta(G)}^{2}+1}{\delta(G)}\rho_{o}(G).$

###### Proof.

Mojdeh et al. [8] showed that the lower bound is true for $\Delta(G)\geq 2$.
So, we just verify the upper bound. Let $v\in V(G)$ be an arbitrary vertex,
then the set of all vertices at distance at most two from $v$ has at most
${\Delta(G)}^{2}+1$ vertices. Thus,
$\rho_{o}(G)\geq\frac{2n}{{\Delta(G)}^{2}+1}$, by the greedy algorithm.
Moreover, $L_{k,t}(G)\leq\frac{kn}{\delta(G)}$ [8], and we get

$\rho_{o}(G)\geq\frac{2n}{{\Delta(G)}^{2}+1}=\frac{2n\delta(G)}{{(\Delta(G)}^{2}+1)\delta(G)}\geq
L_{2,t}(G)\frac{\delta(G)}{{\Delta(G)}^{2}+1}.$

Therefore, we infer that

$L_{2,t}(G)\leq\frac{{\Delta(G)}^{2}+1}{\delta(G)}\rho_{o}(G).$

∎

We can improve the above bounds for trees as follows.

######  Theorem 2.8.

If $T$ is a given tree with $\Delta(T)\geq 2$, then

$\rho_{o}(T)+1\leq L_{2,t}(T)\leq 2\rho_{o}(T).$

Moreover, the following statements hold:

  * (i)

$\rho_{o}(T)+1=L_{2,t}(T)$ if and only if T is a star with at least three
vertices,

  * (ii)

$L_{2,t}(T)=2\rho_{o}(T)$ if and only if for every $L_{2,t}(T)$-set $S$ and
every $\gamma_{t}(T)$-set $D$, we have $|N(s)\cap D|=1$ and $|N(d)\cap S|=2$
for any $s\in S$ and any $d\in D$.

###### Proof.

The lower bound is true for $\Delta(T)\geq 2$. We know that $L_{k,t}(T)\leq
k\gamma_{t}(T)$ ([8]). On the other hand, we have $\rho_{o}(T)=\gamma_{t}(T)$
for every tree $T$ with at least two vertices ([10]). As a consequence, we
have $L_{2,t}(T)\leq 2\gamma_{t}(T)=2\rho_{o}(T)$.

Let $T$ be the star $K_{1,x}$ with $x\geq 2$. Then, $\rho_{o}(T)=2$ and
$L_{2,t}(T)=3$. Therefore, $\rho_{o}(T)+1=L_{2,t}(T)$.

It remains for us to prove the converse. Assume now that $T$ is a tree with
$\rho_{o}(T)+1=L_{2,t}(T)$. We claim that $diam(T)\leq 2$. Suppose to the
contrary that there exist two vertices $v_{1},v_{4}\in V(T)$ such that
$d(v_{1},v_{4})=3$ and let $P=v_{1}v_{2}v_{3}v_{4}$ be the path between them.
Assume that $S_{1}$ is a $\rho_{o}(T)$-set, then $|V(P)\cap S_{1}|\leq 2$. We
now consider three cases as follows.

Case 1. Let $V(P)\cap S_{1}=\emptyset$. Set
$S_{2}=S_{1}\cup\\{v_{1},v_{2}\\}$, we show that $S_{2}$ is a $2$TLP set of
$T$. Since $|N(v_{i})\cap S_{1}|\leq 1$ and
$|N(v_{i})\cap\\{v_{1},v_{2}\\}|\leq 1$ for $1\leq i\leq 4$, it follows that
$|N(v_{i})\cap S_{2}|\leq 2$ for every $v_{i}\in V(P)$. Let now $w$ be a
vertex outside of $P$, so $|N(w)\cap\\{v_{1},v_{2}\\}|\leq 1$ because $T$ has
no cycle. Thus, $|N(w)\cap S_{2}|\leq 2$ for every vertex $w$ outside $P$.
Therefore, we conclude that $S_{2}$ is a $2$TLP set of $T$.

Case 2. Assume $V(P)\cap S_{1}=\\{v_{i}\\}$ for $1\leq i\leq 4$. First, let
$i=1$ or $4$, by using similar techniques as in the previous case,
$S_{1}\cup\\{v_{2},v_{3}\\}$ is a $2$TLP set of $T$. If $i=2$ or $3$, then
$S_{1}\cup\\{v_{1},v_{4}\\}$ is a $2$TLP set of $T$.

Case 3. Suppose $V(P)\cap S_{1}=\\{v_{i},v_{j}\\}$ for some $1\leq i\neq j\leq
4$. If $(i,j)\in\\{(1,2),(1,4),(2,3),(3,4)\\}$, then
$S_{1}\cup\\{v_{3},v_{4}\\}$, $S_{1}\cup\\{v_{2},v_{3}\\}$,
$S_{1}\cup\\{v_{1},v_{4}\\}$ and $S_{1}\cup\\{v_{1},v_{2}\\}$ are $2$TLP sets
of $T$, respectively.

In each case, we observe that $L_{2,t}(T)\geq\rho_{o}(T)+2$, which contradicts
the assumption $\rho_{o}(T)+1=L_{2,t}(T)$. Therefore, we deduce that
$diam(T)\leq 2$, and $T$ is a star with at least three vertices.

Let now $T$ be a tree with $\Delta(T)\geq 2$. As mentioned earlier, we know
that $L_{2,t}(T)=2\rho_{o}(T)$ if and only if $L_{2,t}(T)=2\gamma_{t}(T)$. Let
$S$ be an $L_{2,t}(T)$-set, and $D$ be a $\gamma_{t}(T)$-set. We now restate
the proof of Theorem $7$ in [8]. We set $U=\\{(s,d)\in V(G)\times V(G)|s\in
S,d\in D~{}\text{and}~{}s\in N(d)\\}$, and count the members of $U$ in two
ways. Since $|N(s)\cap D|\geq 1$ for any $s\in S$, it follows that there is at
least one vertex $d\in D$ such that $s\in N(d)$. Thus, $|S|\leq|U|$. On the
other hand, for any $d\in D$ we have $|N(d)\cap S|\leq 2$. Hence, there exists
at most two vertices $s_{1},s_{2}\in S$ such that $s_{1},s_{2}\in N(d)$. So,
we get $|U|\leq 2|D|$, and $|S|\leq 2|D|$. Therefore,
$L_{2,t}(T)=2\gamma_{t}(T)$ if and only if the following statements hold:

  * (1)

for any $s\in S$, we have $|N(s)\cap D|=1$,

  * (ii)

for any $d\in D$, we have $|N(d)\cap S|=2$.

∎

If $diam(G)=1$, then $G$ is a complete graph, and we know that
$L_{2,t}(K_{n})=2$. What can be said about the $2$TLP number of graphs with
diameter $2$? The following theorem is the answer to this question.

######  Theorem 2.9.

If $c\geq 3$ is a positive integer, then there exists a graph $G$ with
$diam(G)=2$ such that $L_{2,t}(G)=c$.

###### Proof.

In what follows, we construct a graph $G$ with diameter $2$ for which
$L_{2,t}(G)=c$. Suppose that $V_{1}=\\{v_{1},v_{2},\cdots,v_{c}\\}$ and
$V_{2}=\\{u_{1},u_{2},\cdots,u_{\frac{c(c-1)}{2}}\\}$ with $V_{1}\cap
V_{2}=\emptyset$. Let $G$ be a graph with vertex set $V(G)=V_{1}\cup V_{2}$
such that $G[V_{1}]=cK_{1}$, $G[V_{2}]=K_{\frac{c(c-1)}{2}}$ and each pair of
distinct vertices in $V_{1}$ has a unique common neighbor in $V_{2}$.
Obviously, $diam(G)=2$. It remains to show that $L_{2,t}(G)=c$. We know
$|V(G)|=c+\frac{c(c-1)}{2}$ and $\Delta(G)=\frac{c(c-1)}{2}+1$. Hence, by
Theorem 2.3, $L_{2,t}(G)\leq|V(G)|+2-\Delta(G)=c+1$. But $G\notin\Omega$, so
$L_{2,t}(G)\leq c$. On the other hand, $V_{1}$ is a $2$TLP set of $G$. Thus,
$L_{2,t}(G)=c$. ∎

######  Theorem 2.10.

Assume that $a\geq 3$ and $b$ are two integers with $a+1\leq b\leq 2a$. Then,
there exists a tree $T$ for which $\rho_{o}(T)=a$ and $L_{2,t}(T)=b$.

###### Proof.

Let $a\geq 3$ and $b$ be two integers such that $a+1\leq b\leq 2a$, and
$b=a+x$ with $1\leq x\leq a$. In what follows, we construct a tree $T$ with
$\rho_{o}(T)=a$ and $L_{2,t}(T)=a+x$ for $a\geq 3$ and $1\leq x\leq a$. We
distinguish two cases based on the value of $x$.

Case 1. First, let $x=a$. Assume $P=v_{1}v_{2}\cdots v_{a}$ is a path. We add
two leaves $u_{i_{1}}$ and $u_{i_{2}}$ to each $v_{i}$, and obtain tree $T$.
Let $S_{1}$ be a $\rho_{o}(T)$-set. If $|S_{1}|\geq a+1$, by the Pigeonhole
principle, there is at least one vertex $v_{i}$ such that $|N(v_{i})\cap
S_{1}|\geq 2$, which is impossible. Hence, $\rho_{o}(T)\leq a$. On the other
hand, $\\{u_{1_{1}},u_{2_{1}},\cdots,u_{a_{1}}\\}$ is a $1$TLP set of $T$, so
$\rho_{o}(T)=a$.

Let $S_{2}$ be an $L_{2,t}(T)$-set. Similarly, if $L_{2,t}(T)\geq 2a+1$, there
exists at least one vertex $v_{i}$ such that $|N(v_{i})\cap S_{2}|\geq 3$, a
contradiction. Thus, $L_{2,t}(T)\leq 2a$. Moreover,
$\\{u_{1_{1}},u_{1_{2}},u_{2_{1}},u_{2_{2}}\cdots,u_{a_{1}},u_{a_{2}}\\}$ is a
$2$TLP set of $T$, hence $L_{2,t}(T)=2a=b$.

Case 2. Suppose now that $1\leq x\leq a-1$. Consider the star
$T^{\prime}=K_{1,a}$ with $V(T^{\prime})=\\{r,v_{1},v_{2},\cdots,v_{a}\\}$ and
deg$(r)=a$. Let $T$ be the tree obtained from $T^{\prime}$ by adding two
leaves $u_{i}$ and $u^{\prime}_{i}$ to each $v_{i}$ for $1\leq i\leq x-1$ and
one leaf $u_{i}$ to each $v_{i}$ for $x\leq i\leq a-1$. We show that
$\rho_{o}(T)=a$ and $L_{2,t}(T)=b$. Since $T\notin\Omega$, it follows that
$L_{2,t}(T)<|V(T)|+2-\Delta(T)$ by Theorem 2.3. Notice that $|V(T)|=2a+x-1$
and $\Delta(T)=a$, thus $L_{2,t}(T)\leq a+x$. On the other hand,
$\\{u_{1},u_{2},\cdots,u_{a-1},u^{\prime}_{1},u^{\prime}_{2},\cdots,u^{\prime}_{x-1},v_{1},v_{a}\\}$
is a $2$TLP set of $T$, so $L_{2,t}(T)=a+x=b$.

Since $T$ is a tree with at least two vertices, $\rho_{o}(T)=\gamma_{t}(T)$
[8]. Moreover, $\\{r,v_{1},v_{2},\cdots,v_{a-1}\\}$ is a TD set of $T$, and
hence $\gamma_{t}(T)\leq a$. Thus, $\rho_{o}(T)\leq a$. It is readily verified
that $\\{u_{1},u_{2},\cdots,u_{a-1},v_{a}\\}$ is a $1$TLP set of $T$.
Therefore, $\rho_{o}(T)=a$. ∎

######  Theorem 2.11.

Let $G$ have a unique $L_{2,t}(G)$-set $B$. Then every leaf of $G$ belongs to
$B$.

###### Proof.

Let $B$ be a unique $L_{2,t}(G)$-set, and let there exist a leaf $l\notin B$
with the support vertex $v$. If $v\in B$ and $|N(v)\cap B|\leq 1$, then
$B^{\prime}=B\cup\\{l\\}$ is a $2$TLP set which is greater than $B$, a
contradiction. So if $v\in B$, then $|N(v)\cap B|=2$. Let $u\in N(v)\cap B$.
We can easily see that $B^{\prime\prime}=(B\backslash\\{u\\})\cup\\{l\\}$ is
an $L_{2,t}(G)$-set, which is impossible because $B$ is unique. Hence $v\notin
B$.

If some neighbor of $v$, say $u^{\prime}$, belongs to $B$, then
$B^{\prime\prime}=(B\backslash\\{u^{\prime}\\})\cup\\{l\\}$ is an
$L_{2,t}(G)$-set. This contradicts the assumption. Therefore, we deduce that
$N[v]\cap B=\emptyset$. So $B\cup\\{l\\}$ is a $2$TLP set, which is a
contradiction with the maximality of $B$. Hence $l\in B$. ∎

##  3 On $2$-(total) limited packing number of some graph products

######  Theorem 3.1.

For any graphs $G$ and $H$, $L_{2,t}(G\square
H)\geq\max\\{L_{2,t}(G)\rho(H),\rho(G)L_{2,t}(H)\\}$. Moreover, this bound is
sharp.

###### Proof.

Let $P_{G}$ and $P_{H}$ be an $L_{2,t}(G)$-set and a $\rho(H)$-set,
respectively. Set $P=P_{G}\times P_{H}$, and suppose to the contrary that $P$
is not a $2$TLP set of $G\square H$. Therefore, there exists a vertex
$(x,y)\in V(G)\times V(H)$ adjacent to three distinct vertices
$(g_{1},h_{1}),(g_{2},h_{2}),(g_{3},h_{3})\in P$. We distinguish the following
cases.

Case 1. $h_{1}=h_{2}=h_{3}$. If $y$ is adjacent to $h_{1}$, then
$x=g_{1}=g_{2}=g_{3}$, which is impossible. So, $y=h_{1}=h_{2}=h_{3}$. In such
a situation, $x$ is adjacent to $g_{1},g_{2},g_{3}\in P_{G}$, which
contradicts the fact that $P_{G}$ is a $2$TLP set in $G$.

Case 2. At least two vertices from $\\{h_{1},h_{2},h_{3}\\}$, say $h_{1}$ and
$h_{2}$, are distinct. By the adjacency rule of the Cartesian product graphs,
we deduce that $\\{h_{1},h_{2}\\}\subseteq N_{H}[y]\cap P_{H}$. This
contradicts the fact that $P_{H}$ is a packing in $H$.

Therefore, $P$ is a $2$TLP set in $G\square H$. Hence, $L_{2,t}(G\square
H)\geq|P|=L_{2,t}(G)\rho(H)$. Similarly, we have $L_{2,t}(G\square
H)\geq\rho(G)L_{2,t}(H)$.

We can show that this bound is sharp in the following way. Let $G^{\prime}$ be
any connected graph on the set of vertices
$\\{v_{1}^{\prime},\cdots,v_{n}^{\prime}\\}$. Let $G=G^{\prime}\odot K_{1}$,
in which $N_{G}(v_{i}^{\prime})\setminus
N_{G^{\prime}}(v_{i}^{\prime})=\\{v_{i}\\}$ for each $1\leq i\leq n$. We now
consider the graph $G\square K_{r}$ for $r\geq 3$, and let $Q$ be an
$L_{2,t}(G\square K_{r})$-set. It is not difficult to see that
$|Q\cap\big{(}\\{v_{i},v_{i}^{\prime}\\}\times V(K_{r})\big{)}|\leq 2$ for
each $1\leq i\leq n$. This implies that

$\begin{array}[]{lcl}L_{2,t}(G)&=&|Q|=|Q\cap V(G\square
K_{r})|=|Q\cap\big{(}\cup_{i=1}^{n}(\\{v_{i},v_{i}^{\prime}\\}\times
V(K_{r}))\big{)}|\\\
&=&\sum_{i=1}^{n}|Q\cap\big{(}\\{v_{i},v_{i}^{\prime}\\}\times
V(K_{r})\big{)}|\leq 2n=L_{2,t}(K_{r})\rho(G).\end{array}$ (1)

∎

######  Theorem 3.2.

Let $G$ and $H$ be graphs with $i_{G}$ and $i_{H}$ isolated vertices,
respectively. Then,

$L_{2,t}(G\times H)\geq
max~{}\\{\rho_{o}(G^{-})L_{2,t}(H^{-}),L_{2,t}(G^{-})\rho_{o}(H^{-})\\}+i_{G}|V(H)|+i_{H}|V(G)|-i_{G}i_{H}$

and this bound is sharp.

###### Proof.

Suppose first that $G$ and $H$ are graphs without isolated vertices. Let
$P_{G}$ and $P_{H}$ be a $\rho_{o}(G)$-set and an $L_{2,t}(H)$-set,
respectively. Set $P=P_{G}\times P_{H}$, and assume for the sake of
contradiction that $P$ is not a $2$TLP set of $G\times H$. Hence, there exists
a vertex $(x,y)\in V(G\times H)$ adjacent to three distinct vertices
$(g,h),(g^{\prime},h^{\prime}),(g^{\prime\prime},h^{\prime\prime})\in P$. Then
$g=g^{\prime}=g^{\prime\prime}$ because $P_{G}$ is a $\rho_{o}(G)$-set. So
$h\neq h^{\prime}\neq h^{\prime\prime}$ and $|N(y)\cap P_{H}|\geq 3$, a
contradiction. Therefore, $P$ is a $2$TLP set in $G\times H$, and
$L_{2,t}(G\times H)\geq|P|=\rho_{o}(G)L_{2,t}(H)$. We have $L_{2,t}(G\times
H)\geq L_{2,t}(G)\rho_{o}(H)$ by a similar fashion.

We have

$L_{2,t}(G\times H)=L_{2,t}(G^{-}\times
H^{-})+i_{G}|V(H)|+i_{H}|V(G)|-i_{G}i_{H}.$

Therefore,

$L_{2,t}(G\times H)\geq
max~{}\\{\rho_{o}(G^{-})L_{2,t}(H^{-}),L_{2,t}(G^{-})\rho_{o}(H^{-})\\}+i_{G}|V(H)|+i_{H}|V(G)|-i_{G}i_{H}.$

In what follows, we show that this bound is sharp. Let $G$ be a bipartite
graph without isolated vertices. Then, $L_{2,t}(G\times
K_{2})=L_{2,t}(2G)=2L_{2,t}(G)$. On the other hand, $L_{2,t}(G\times
K_{2})\geq
max~{}\\{\rho_{o}(G)L_{2,t}(K_{2}),L_{2,t}(G)\rho_{o}(K_{2})\\}=max~{}\\{2\rho_{o}(G),2L_{2,t}(G)\\}=2L_{2,t}(G)$.
∎

######  Theorem 3.3.

Let $G$ be a graph of order $n$ with $i_{G}$ isolated vertices. If $H$ is a
rooted graph at $v$, then

$n(L_{2,t}(H)-1)+i_{G}\leq L_{2,t}(G\circ_{v}H)\leq nL_{2,t}(H).$

Furthermore, these bounds are sharp.

###### Proof.

Note that any $H$-layer in $G\circ_{v}H$ is isomorphic to $H$. So, each
$L_{2,t}(G\circ_{v}H)$-set intersects every $H$-layer is at most $L_{2,t}(H)$
vertices. Hence, $L_{2,t}(G\circ_{v}H)\leq nL_{2,t}(H)$. On the other side,
let $P_{H}$ be an $L_{2,t}(H)$-set. We can readily observe that
$P=\bigcup_{g\in V(G)}\big{(}\\{g\\}\times(P_{H}\backslash\\{v\\})\big{)}$ is
a $2$TLP set in $G\circ_{v}H$, so we have $n(L_{2,t}(H)-1)\leq|P|\leq
L_{2,t}(G\circ_{v}H)$.

Suppose that there exists an $L_{2,t}(H)$-set $P_{H}$ not consisting of $v$.
Notice that $P=\bigcup_{g\in V(G)}\big{(}\\{g\\}\times P_{H}\big{)}$ is a
$2$TLP set in $G\circ_{v}H$, and we have $nL_{2,t}(H)=|P|\leq
L_{2,t}(G\circ_{v}H)$. Thus, we conclude that
$L_{2,t}(G\circ_{v}H)=nL_{2,t}(H)$ in this case.

Assume now that $v$ has degree two in all subgraphs induced by every
$L_{2,t}(H)$-set $P_{H}$, that is $deg_{H[P_{H}]}(v)=2$. Suppose that for
every $2$TLP set $P^{\prime}_{H}$ in $H$, $|P^{\prime}_{H}\backslash N[v]|\leq
L_{2,t}(H)-3$. Assume that $P$ is an $L_{2,t}(G\circ_{v}H)$-set. Note that
exactly $i_{G}$ components of $G\circ_{v}H$ are isomorphic to $H$, which
implies that every component has exactly $L_{2,t}(H)$ vertices in $P$.
Moreover, we have one component isomorphic to $G^{-}\circ_{v}H$. Let
$P^{-}=P\cap(G^{-}\circ_{v}H)$ and $P^{-}_{g}=P^{-}\cap{}^{g}\\!H$ for every
$g\in V(G^{-})$. We now show that
$L_{2,t}(G^{-}\circ_{v}H)=(n-i_{G})(L_{2,t}(H)-1)$. Assume that
$L_{2,t}(G^{-}\circ_{v}H)>(n-i_{G})(L_{2,t}(H)-1)$. Hence, there exists at
least one vertex $g_{1}\in V(G^{-})$ for which $|P^{-}_{g_{1}}|=L_{2,t}(H)$.
Otherwise, $|P^{-}|=\sum_{g_{i}\in V(G^{-})}|P^{-}_{g_{i}}|\leq\sum_{g_{i}\in
V(G^{-})}L(_{2,t}(H)-1)=(n-i_{G})(L_{2,t}(H)-1)$, which is a contradiction.

Since $G^{-}$ has no isolated vertex, there exists a vertex $g_{2}\in
V(G^{-})$ for which $g_{1}g_{2}\in E(G)$. If $|P^{-}_{g_{2}}|=L_{2,t}(H)$,
then both $(g_{1},v)$ and $(g_{2},v)$ have three neighbors in $P^{-}$, which
is impossible. Therefore $|P^{-}_{g_{2}}|\leq L_{2,t}(H)-1$ for all $g_{2}\in
N_{G}(g_{1})$. Now let $g_{2}$ be an arbitrary neighbor of $g_{1}$ in $G^{-}$.
If $|P^{-}_{g_{2}}|=L_{2,t}(H)-1$, then
$|N_{(G\circ_{v}H)[{}^{g_{2}}\\!H]}[(g_{2},v)]\cap P^{-}_{g_{2}}|=2$. This
implies that $|N_{(G^{-}\circ_{v}H)}(g_{1},v)\cap P^{-}|\geq 3$ or
$|N_{(G^{-}\circ_{v}H)}(g_{2},v)\cap P^{-}|\geq 3$, a contradiction. Thus,
$|P^{-}_{g_{2}}|\leq L_{2,t}(H)-2$ for all $g_{2}\in N_{G}(g_{1})$.

The above argument provides a guarantee that for every vertex $g_{1}\in V(G)$
such that $|P^{-}_{g_{1}}|=L_{2,t}(H)$, we have $|P^{-}_{g_{2}}|\leq
L_{2,t}(H)-2$ for all $g_{2}\in N_{G}(g_{1})$. This implies that

$L_{2,t}(G^{-}\circ_{v}H)\leq\frac{n-i_{G}}{2}L_{2,t}(H)+\frac{n-i_{G}}{2}(L_{2,t}(H)-2)=(n-i_{G})(L_{2,t}(H)-1),$

which contradicts the assumption
$L_{2,t}(G^{-}\circ_{v}H)>(n-i_{G})(L_{2,t}(H)-1)$. So
$L_{2,t}(G^{-}\circ_{v}H)\leq(n-i_{G})(L_{2,t}(H)-1)$. It follows that
$L_{2,t}(G^{-}\circ_{v}H)=(n-i_{G})(L_{2,t}(H)-1)$ by using the corresponding
inequality obtained from the first steps of the proof. Therefore,
$L_{2,t}(G\circ_{v}H)=L_{2,t}(G^{-}\circ_{v}H)+i_{G}L_{2,t}(H)=(n-i_{G})(L_{2,t}(H)-1)+i_{G}L_{2,t}(H)=n(L_{2,t}(H)-1)+i_{G}$.
∎

######  Theorem 3.4.

For any graphs $G$ and $H$,

$L_{2}(G\square H)\leq\min\\{L_{2}(G)|V(H)|,L_{2}(H)|V(G)|\\},$

and this bound is sharp.

###### Proof.

Let $V(H)=\\{v_{1},v_{2},\cdots,v_{|V(H)|}\\}$. It is obvious that $G\square
H$ contains $|V(H)|$ disjoint $G$-layers. Suppose now that $P$ is an
$L_{2}(G\square H)$-set, thus $P_{i}=P\cap G^{v_{i}}$ is a $2$LP set in
$(G\square H)[G^{v_{i}}]$ for each $1\leq i\leq|V(H)|$. Therefore,
$|P_{i}|\leq L_{2}(G)$, which leads to

$L_{2}(G\square H)=|P|=\sum_{i=1}^{|V(H)|}|P_{i}|\leq L_{2}(G)|V(H)|.$

Similarly, we have $L_{2}(G\square H)\leq L_{2}(H)|V(G)|$.

For sharpness consider $G=P_{2}$ and $H=K_{m,n}$ for $m,n\geq 2$. We observe
that $L_{2}(K_{m,n})=2$ [5], and $L_{2}(P_{2})=2$. It is easy to see that
$L_{2}(G\square H)=4$. ∎

######  Theorem 3.5.

Let $G$ and $H$ be graphs with $i_{G}$ and $i_{H}$ isolated vertices,
respectively. Then,

$L_{2}(G\times H)\geq
max~{}\\{\rho_{o}(G^{-})L_{2}(H^{-}),L_{2}(G^{-})\rho_{o}(H^{-}),\rho(G^{-})L_{2,t}(H^{-}),L_{2,t}(G^{-})\rho(H^{-})\\}$

$+i_{G}|V(H)|+i_{H}|V(G)|-i_{G}i_{H}$.

Moreover, this bound is sharp.

###### Proof.

Assume first that $G$ and $H$ are graphs without isolated vertices. Let
$P_{G}$, $P^{\prime}_{G}$, $P_{H}$ and $P^{\prime}_{H}$ be an
$L_{2,t}(G)$-set, a $\rho_{o}(G)$-set, a $\rho(H)$-set and an $L_{2}(H)$-set,
respectively. Set $P=P_{G}\times P_{H}$ and $P^{\prime}=P^{\prime}_{G}\times
P^{\prime}_{H}$, and suppose to the contrary that $P$ and $P^{\prime}$ are not
$2$LP sets of $G\times H$. So there exist vertices $(x,y)$,
$(x^{\prime},y^{\prime})\in V(G\times H)$ such that $|N[(x,y)]\cap P|\geq 3$
and $|N[(x^{\prime},y^{\prime})]\cap P^{\prime}|\geq 3$, respectively.

If $(x,y)\in P$, then $(x,y)$ is adjacent to two distinct vertices
$(g,h),(g^{\prime},h^{\prime})\in P$. So $|N[y]\cap P_{H}|\geq 2$, which is
impossible. If $(x,y)\in V(G\times H)\backslash P$, then $(x,y)$ is adjacent
to three distinct vertices
$(g,h),(g^{\prime},h^{\prime}),(g^{\prime\prime},h^{\prime\prime})\in P$. We
observe that $h=h^{\prime}=h^{\prime\prime}$ because $P_{H}$ is a
$\rho(H)$-set. Hence $g\neq g^{\prime}\neq g^{\prime\prime}$ and $|N(x)\cap
P_{G}|\geq 3$, a contradiction. Therefore, $P$ is a $2$LP set in $G\times H$
and $L_{2}(G\times H)\geq|P|\geq L_{2,t}(G)\rho(H)$. We have $L_{2}(G\times
H)\geq\rho(G)L_{2,t}(H)$ by a similar method.

If $(x^{\prime},y^{\prime})\in P^{\prime}$, then $(x^{\prime},y^{\prime})$ is
adjacent to two distinct vertices $(g_{1},h_{1}),(g_{2},h_{2})\in P^{\prime}$.
We have $g_{1}=g_{2}$ because $P^{\prime}_{G}$ is a $\rho_{o}(G)$-set. Thus,
$h_{1}\neq h_{2}$ and $|N[y^{\prime}]\cap P^{\prime}_{H}|\geq 3$, which is
impossible. If $(x^{\prime},y^{\prime})\in V(G\times H)\backslash P^{\prime}$,
then $(x^{\prime},y^{\prime})$ is adjacent to three distinct vertices
$(g_{1},h_{1}),(g_{2},h_{2}),(g_{3},h_{3})\in P^{\prime}$. $g_{1}=g_{2}=g_{3}$
since $P^{\prime}_{G}$ is a $\rho_{o}(G)$-set, so $h_{1}\neq h_{2}\neq h_{3}$
and $|N[y^{\prime}]\cap P^{\prime}_{H}|\geq 3$, a contradiction. Therefore
$P^{\prime}$ is a $2$LP set in $G\times H$, and $L_{2}(G\times
H)\geq\rho_{o}(G)L_{2}(H)$. We get $L_{2}(G\times H)\geq L_{2}(G)\rho_{o}(H)$
by a similar fashion. Therefore,

$L_{2}(G\times H)\geq
max~{}\\{\rho_{o}(G)L_{2}(H),L_{2}(G)\rho_{o}(H),\rho(G)L_{2,t}(H),L_{2,t}(G)\rho(H)\\}.$

We now suppose that $G$ and $H$ are arbitrary graphs. Then,

$L_{2}(G\times H)=L_{2}(G^{-}\times
H^{-})+i_{G}|V(H)|+i_{H}|V(G)|-i_{G}i_{H}\geq$
$max~{}\\{\rho_{o}(G^{-})L_{2}(H^{-}),L_{2}(G^{-})\rho_{o}(H^{-}),\rho(G^{-})L_{2,t}(H^{-}),L_{2,t}(G^{-})\rho(H^{-})\\}+$
$i_{G}|V(H)|+i_{H}|V(G)|-i_{G}i_{H}.$

In what follows, we show the sharpness of this bound. Let $G$ be a bipartite
graph without isolated vertices. Then, $L_{2}(G\times
K_{2})=L_{2}(2G)=2L_{2}(G)$. On the other hand,

$L_{2}(G\times K_{2})\geq
max~{}\\{\rho_{o}(G)L_{2}(K_{2}),L_{2}(G)\rho_{o}(K_{2}),\rho(G)L_{2,t}(K_{2}),L_{2,t}(G)\rho(K_{2})\\}=$
$max~{}\\{2\rho_{o}(G),2L_{2}(G),2\rho(G),L_{2,t}(G)\\}=2L_{2}(G).$

∎

We end this section by studying the $2$LP number of rooted product graphs.

######  Theorem 3.6.

Let $G$ be a graph of order $n$. If $H$ is a graph with root $v$, then

$L_{2}(G\circ_{v}H)=\begin{cases}L_{2}(G)+n(L_{2}(H)-1)\quad\text{if}~{}v\in
P_{H}~{}\text{for every}~{}L_{2}(H)\text{-set}~{}P_{H},\\\
nL_{2}(H)\qquad~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{if}~{}v\notin
P_{H}~{}\text{for some}~{}L_{2}(H)\text{-set}~{}P_{H}.\end{cases}$

###### Proof.

We consider two cases based on the membership of $v$ to $L_{2}(H)$-sets.

Case 1. Assume that $v$ belongs to any $L_{2}(H)$-set $P_{H}$, and
$P^{\prime}$ be an $L_{2}(G)$-set. Set
$P=(P^{\prime}\times\\{v\\})\cup\big{(}V(G)\times(P_{H}\backslash\\{v\\})\big{)}$.
It can be readily seen that $P$ is a $2$LP set in $G\circ_{v}H$. Therefore,
$L_{2}(G\circ_{v}H)\geq|P^{\prime}\times\\{v\\}|+|V(G)\times(P_{H}\backslash\\{v\\})|=L_{2}(G)+n(L_{2}(H)-1)$.

On the other hand, let $B$ be an $L_{2}(G\circ_{v}H)$-set. Then
$B_{g}=B\cap{}^{g}\\!H$ is a $2$LP set in $(G\circ_{v}H)[{}^{g}\\!H]$ for
every $g\in V(G)$. Note that $B_{g}$ is not an
$L_{2}((G\circ_{v}H)[{}^{g}\\!H])$-set for some $g\in V(G)$ since $v$ belongs
to every $L_{2}(H)$-set. Hence, $|B\cap{}^{g}\\!H|=|B_{g}|\leq L_{2}(H)-1$ if
$(g,v)\notin B$, which means $|B\cap({}^{g}\\!H|\backslash\\{(g,v)\\})|\leq
L_{2}(H)-1$. Also if $(g,v)\in B$, then
$|B\cap({}^{g}\\!H|\backslash\\{(g,v)\\})|\leq L_{2}(H)-1$ as well. In
addition, $B\cap G^{v}$ is a $2$LP set in $(G\circ_{v}H)[G^{v}]$. Thus,
$|B\cap G^{v}|\leq L_{2}(G)$, and we have

$L_{2}(G\circ_{v}H)=|B|=|B\cap G^{v}|+\sum_{g\in
V(G)}|B\cap({}^{g}\\!H|\backslash\\{(g,v)\\})|\leq L_{2}(G)+n(L_{2}(H)-1).$

Therefore, $L_{2}(G\circ_{v}H)=L_{2}(G)+n(L_{2}(H)-1)$.

Case 2. Assume that there exists an $L_{2}(H)$-set $P_{H}$ for which $v\notin
P_{H}$. Let ${}^{g}\\!P_{H}=\\{g\\}\times P_{H}$ for every $g\in V(G)$, and
let $P^{\prime\prime}=\cup_{g\in V(G)}{}^{g}\\!P_{H}$. We can easily see that
$P^{\prime\prime}$ is a $2$LP set in $G\circ_{v}H$, so
$L_{2}(G\circ_{v}H)\geq|P^{\prime\prime}|=nL_{2}(H)$. On the other hand, let
$P$ be an $L_{2}(G\circ_{v}H)$-set. We can easily observe that the set
$P_{g}=P\cap{}^{g}\\!H$ is a $2$LP set in $(G\circ_{v}H)[{}^{g}\\!H]$ for
every $g\in V(G)$. So $L_{2}(H)=L_{2}(G\circ_{v}H)[{}^{g}\\!H]\geq|P_{g}|$.
Therefore, $L_{2}(G\circ_{v}H)=|P|=\sum_{g\in V(G)}|P_{g}|\leq\sum_{g\in
V(G)}L_{2}(H)=nL_{2}(H)$. This leads to $L_{2}(G\circ_{v}H)=nL_{2}(H)$. ∎

##  4 Results on vertex partitioning into $2$-limited packings

######  Theorem 4.1.

If $G$ is a graph of order $n\geq 2$, then $\chi_{\times k}(G)\geq
2\sqrt{n}-L_{k}(G)$.

###### Proof.

We first prove that $\chi_{\times k}(G)\times L_{k}(G)\geq n$. Let
$\\{B_{1},B_{2},\cdots,B_{\chi_{\times k}(G)}\\}$ be a $k$LPP of $G$. Then,

$\chi_{\times k}(G)\times L_{k}(G)=\sum_{i=1}^{\chi_{\times
k}(G)}L_{k}(G)\geq\sum_{i=1}^{\chi_{\times k}(G)}|B_{i}|=n$

and equality holds when each set $B_{i}$ is an $L_{k}(G)$-set. So
$\chi_{\times k}(G)+L_{k}(G)\geq\chi_{\times k}(G)+\frac{n}{\chi_{\times
k}(G)}$.

On the other hand, $\chi_{\times k}(G)\leq\frac{n}{k}$ because every subset of
$V(G)$ of cardinality at most $k$ is a $k$LP set. We observe that the function
$g(x)=x+\frac{n}{x}$ is decreasing for $1\leq x\leq\sqrt{n}$, and it is
increasing for $\sqrt{n}\leq x\leq\frac{n}{k}$. Therefore $\chi_{\times
k}(G)+L_{k}(G)\geq 2\sqrt{n}$.

This bound is sharp for the complete graph $K_{4}$, the cycle $C_{4}$ and the
star $S_{4}$. ∎

The corona product of two graphs $G$ with $V(G)={v_{1},...,v_{n}}$ and $H$ is
defined as the graph created by taking one copy of $G$, $|V(G)|$ copies of $H$
and joining $v_{i}\in V(G)$ to any vertex in the $i^{th}$ copy of $H$. The
corona product of the graphs $G$ and $H$ is denoted by $G\odot H$.

If $v$ is a vertex of maximum degree in $G$, then $N_{G\odot
H}[v]=\Delta(G)+1+|V(H)|$. So we need at least
$\lceil\frac{\Delta(G)+1+|V(H)|}{2}\rceil$ $2$-limited packing sets in every
2LPP of $G\odot H$. Therefore $\chi_{\times 2}(G\odot
H)\geq\lceil\frac{\Delta(G)+1+|V(H)|}{2}\rceil$.

######  Theorem 4.2.

If $G$ and $H$ are two graphs, then

$\chi_{\times 2}(G\odot H)\in\\{\chi_{\times 2}(G),\chi_{\times
2}(G)+1,\chi_{\times 2}(G)+2,\cdots,\chi_{\times
2}(G)+\lceil\frac{|V(H)|}{2}\rceil\\}.$

###### Proof.

Let $V(G)=\\{v_{1},v_{2},\cdots,v_{n}\\}$ and
$V(H)=\\{u_{1},u_{2},\cdots,u_{n^{\prime}}\\}$, and let
$\mathbb{P}=\\{P_{1},P_{2},\cdots,P_{\chi_{\times 2}(G)}\\}$ be a $2$LPP of
$G$.

Since $G$ is a subgraph of $G\odot H$, $\chi_{\times 2}(G)\leq\chi_{\times
2}(G\odot H)$. That $\chi_{\times 2}(G\odot H)=\chi_{\times 2}(G)$ can be seen
as follows. If $|N_{G}[v_{i}]\cap(\cup_{j=1}^{\chi_{\times 2}(G)}P_{j})|\leq
2\chi_{\times 2}(G)-n^{\prime}$ for each $v_{i}\in V(G)$, then we place the
vertices of each copy of $H$ in the members of $\mathbb{P}$ such that
$|N_{G\odot H}[v_{i}]\cap P_{j})|\leq 2$ for each $1\leq i\leq n$ and $1\leq
j\leq\chi_{\times 2}(G)$. So the equality holds.

We now have two cases based on the behavior of $|V(H)|$ and prove the upper
bound.
$\bullet$ Let $|V(H)|$ be even. In the worst case, if there exists a vertex
$v_{i}\in V(G)$ such that $2\chi_{\times
2}(G)-1\leq|N_{G}[v_{i}]\cap(\cup_{j=1}^{\chi_{\times 2}(G)}P_{j})|\leq
2\chi_{\times 2}(G)$, then we add new sets $P_{\chi_{\times
2}(G)+1},P_{\chi_{\times 2}(G)+2},\cdots,P_{\chi_{\times
2}(G)+\lceil\frac{|V(H)|}{2}\rceil}$ to $\mathbb{P}$ and put the vertices of
each copy of $H$ in these sets two by two until there are no vertices left.
Therefore $\chi_{\times 2}(G\odot H)=\chi_{\times
2}(G)+\lceil\frac{|V(H)|}{2}\rceil$.
$\bullet$ Let $|V(H)|$ be odd. If there exists a vertex $v_{i}\in V(G)$ such
that $|N_{G}[v_{i}]\cap(\cup_{j=1}^{\chi_{\times 2}(G)}P_{j})|=2\chi_{\times
2}(G)$, then $\chi_{\times 2}(G\odot H)=\chi_{\times
2}(G)+\lceil\frac{|V(H)|}{2}\rceil$ as before. Hence $\chi_{\times
2}(G)\leq\chi_{\times 2}(G\odot H)\leq\chi_{\times
2}(G)+\lceil\frac{|V(H)|}{2}\rceil$.

In what follows, we show that $\chi_{\times 2}(G\odot H)$ can take all values
between $\chi_{\times 2}(G)$ and $\chi_{\times
2}(G)+\lceil\frac{|V(H)|}{2}\rceil$. It is enough to consider the graph $G$ as
$K_{a,a}$ and graph $H$ as $\overline{K_{a+b-1}}$ for $a\geq 1$ and $b\geq 0$.
Let $\mathbb{P}=\\{P_{1},P_{2},\cdots,P_{\chi_{\times 2}(G)}\\}$ be a $2$LPP
of $G$. If $v_{i}\in V(G)$ belongs to $P_{j}$, then $v_{i}$ has the label $j$.
We first show that $\chi_{\times 2}(G\odot H)=\chi_{\times
2}(G)+\lceil\frac{b}{2}\rceil$. We assign the labels from $\\{1,2,\cdots,a\\}$
to the vertices of $G$ as shown in Figure 2, which is equivalent to a $2$LPP
for $G$ with the smallest cardinality.

$1$$2$$3$$4$$a$$1$$2$$3$$4$$a$ Figure 2: the labeling of $V(G)$.

We have $N_{G\odot H}[v_{i}]=N_{G}(v_{i})+1+|V(H)|=2a+b$ for each $v_{i}\in
V(G)$. $(a+1)$ closed neighbors of each $v_{i}\in V(G)$ are labeled as above.
If $v_{i}\in P_{k}$, i.e., $v_{i}$ has label $k$, then $|N_{G}[v_{i}]\cap
P_{k}|=2$ and $|N_{G}[v_{i}]\cap P_{j}|=1$ for each $j\neq k$, as we see in
figure 2. It is clear that $j$ has $a-1$ values. We put $(a-1)$ unlabeled
neighbors of $v_{i}$ one by one in the sets $P_{j}$ with the previous
condition. Thus, $b$ vertices are still unlabeled. We consider the new labels
$a+1,a+2,\cdots,a+\lceil\frac{b}{2}\rceil$, and then label the remaining $b$
vertices two by two with them. Therefore, $\chi_{\times 2}(G\odot
H)=\chi_{\times 2}(G)+\lceil\frac{b}{2}\rceil$.

Note that if $a=1$ and $b\geq 1$, then $\chi_{\times 2}(G\odot H)=\chi_{\times
2}(G)+\lceil\frac{b+1-1}{2}\rceil=\chi_{\times
2}(G)+\lceil\frac{|V(H)|}{2}\rceil$. If $b=0$, then $\chi_{\times 2}(G\odot
H)=\chi_{\times 2}(G)$. ∎

##  5 Concluding remarks

We have bounded $\chi_{\times 2}$ for some product graphs in our paper. It may
be of interest to provide the exact value of this parameter and either improve
or bound it for other product graphs.

## References

  * [1] A. S. Ahmadi, N. Soltankhah, and B. Samadi,  Limited packings: related vertex partitions and duality issues, Appl Math Comput. 472 (2024).
  * [2] Xuqing Bai, H. Chang and X. Li, More on limited packings in graphs, J. Comb. Optim. 40 (2020), 412–430.
  * [3] E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977), 247–261.
  * [4] A. Gagarin and V. Zverovich, The probabilistic approach to limited packings in graphs, Discrete Appl. Math. 184 (2015), 146–153.
  * [5] R. Gallant, G. Gunther, B.L. Hartnell and D.F. Rall, Limited packing in graphs, Discrete Appl. Math. 158 (2010), 1357–1364.
  * [6] T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Domination in Graphs: Core Concepts, Springer Monographs in Mathematics, Springer, Cham, 2023.
  * [7] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs, New York, Marcel Dekker, 1998.
  * [8] S.M. Hosseini Moghaddam, D.A. Mojdeh and B. Samadi, Total limited packing in graphs, Fasc. Math. 56 (2016), 121–127.
  * [9] D.A. Mojdeh, I. Peterin, B. Samadi and I.G. Yero, (Open) packing number of some graph products, Discret. Math. Theor. Comput. Sci. 22 (2019).
  * [10] D. Rall,  Total domination in categorical products of graphs, Discussiones mathematicae graph theory. 25(1-2) (2005), 35–44
  * [11] B. Samadi,  On the $k$-limited packing numbers in graphs, Discrete Optim. 22 (2016), 270–276.
  * [12] D.B. West, Introduction to Graph Theory (Second Edition), Prentice Hall, USA, 2001.