* [201] I. W. Stewart et al., “XCone: N-jettiness as an Exclusive Cone Jet Algorithm”,  JHEP 11 (2015) 072, doi:10.1007/JHEP11(2015)072, arXiv:1508.01516.
  * [202] J. Thaler and T. F. Wilkason, “Resolving Boosted Jets with XCone”,  JHEP 12 (2015) 051, doi:10.1007/JHEP12(2015)051, arXiv:1508.01518.
  * [203] T. Lapsien, R. Kogler, and J. Haller, “A new tagger for hadronically decaying heavy particles at the LHC”,  Eur. Phys. J. C 76 (2016) 600, doi:10.1140/epjc/s10052-016-4443-8, arXiv:1606.04961.
  * [204] B. Mukhopadhyaya, T. Samui, and R. K. Singh, “Dynamic radius jet clustering algorithm”,  JHEP 04 (2023) 019, doi:10.1007/JHEP04(2023)019, arXiv:2301.13074.
  * [205] A. J. Larkoski, D. Rathjens, J. Veatch, and J. W. Walker, “Jet SIFT-ing: a new scale-invariant jet clustering algorithm for the substructure era”, arXiv:2302.08609.
  * [206] X. Ju and B. Nachman, “Supervised Jet Clustering with Graph Neural Networks for Lorentz Boosted Bosons”,  Phys. Rev. D 102 (2020) 075014, doi:10.1103/PhysRevD.102.075014, arXiv:2008.06064.
  * [207] S. Mondal, G. Barone, and A. Schmidt, “PAIReD jet: A multi-pronged resonance tagging strategy across all Lorentz boosts”, arXiv:2311.11011.
  * [208] B. Nachman and C. Shimmin, “AI Safety for High Energy Physics”, arXiv:1910.08606.
  * [209] D. Yallup and W. Handley, “Hunting for bumps in the margins”,  JINST 18 (2023) P05014, doi:10.1088/1748-0221/18/05/P05014, arXiv:2211.10391.
  * [210] A. Butter, B. M. Dillon, T. Plehn, and L. Vogel, “Performance versus resilience in modern quark-gluon tagging”,  SciPost Phys. Core 6 (2023) 085, doi:10.21468/SciPostPhysCore.6.4.085, arXiv:2212.10493.
  * [211] E. M. Metodiev, B. Nachman, and J. Thaler, “Classification without labels: Learning from mixed samples in high energy physics”,  JHEP 10 (2017) 174, doi:10.1007/JHEP10(2017)174, arXiv:1708.02949.
  * [212] A. Andreassen, I. Feige, C. Frye, and M. D. Schwartz, “JUNIPR: a Framework for Unsupervised Machine Learning in Particle Physics”,  Eur. Phys. J. C 79 (2019) 102, doi:10.1140/epjc/s10052-019-6607-9, arXiv:1804.09720.
  * [213] P. T. Komiske, E. M. Metodiev, B. Nachman, and M. D. Schwartz, “Learning to classify from impure samples with high-dimensional data”,  Phys. Rev. D 98 (2018) 011502, doi:10.1103/PhysRevD.98.011502, arXiv:1801.10158.
  * [214] E. Alvarez et al., “Exploring unsupervised top tagging using Bayesian inference”,  SciPost Phys. Core 6 (2023) 046, doi:10.21468/SciPostPhysCore.6.2.046, arXiv:2212.13583.
  * [215] A. Stein et al., “Improving Robustness of Jet Tagging Algorithms with Adversarial Training”,  Comput. Softw. Big Sci. 6 (2022) 15, doi:10.1007/s41781-022-00087-1, arXiv:2203.13890.
  * [216] CMS Collaboration, “Adversarial training for b-tagging algorithms in CMS”, CMS Detector Performance Note CMS-DP-2022-049, 2022.
  * [217] P. T. Komiske, E. M. Metodiev, and J. Thaler, “Energy flow polynomials: A complete linear basis for jet substructure”,  JHEP 04 (2018) 013, doi:10.1007/JHEP04(2018)013, arXiv:1712.07124.
  * [218] C. Grojean, A. Paul, and Z. Qian, “Resurrecting $b\overline{b}h$ with kinematic shapes”,  JHEP 04 (2021) 139, doi:10.1007/JHEP04(2021)139, arXiv:2011.13945.
  * [219] A. Bogatskiy et al., “Lorentz Group Equivariant Neural Network for Particle Physics”, arXiv:2006.04780.
  * [220] J. M. Munoz, I. Batatia, and C. Ortner, “Boost invariant polynomials for efficient jet tagging”,  Mach. Learn. Sci. Tech. 3 (2022) 04LT05, doi:10.1088/2632-2153/aca9ca, arXiv:2207.08272.
  * [221] O. Fedkevych, C. K. Khosa, S. Marzani, and F. Sforza, “Identification of b jets using QCD-inspired observables”,  Phys. Rev. D 107 (2023) 034032, doi:10.1103/PhysRevD.107.034032, arXiv:2202.05082.
  * [222] B. Bhattacherjee, C. Bose, A. Chakraborty, and R. Sengupta, “Boosted top tagging and its interpretation using Shapley values”, arXiv:2212.11606.
  * [223] L. Bradshaw, S. Chang, and B. Ostdiek, “Creating simple, interpretable anomaly detectors for new physics in jet substructure”,  Phys. Rev. D 106 (2022) 035014, doi:10.1103/PhysRevD.106.035014, arXiv:2203.01343.
  * [224] R. Das, G. Kasieczka, and D. Shih, “Feature Selection with Distance Correlation”, arXiv:2212.00046.
  * [225] P. Cal, J. Thaler, and W. J. Waalewijn, “Power counting energy flow polynomials”,  JHEP 09 (2022) 021, doi:10.1007/JHEP09(2022)021, arXiv:2205.06818.
  * [226] ATLAS Collaboration, “Calibration of the $b$-tagging efficiency on charm jets using a sample of $W$+$c$ events with $\sqrt{s}$ = 13 TeV ATLAS data”, ATLAS Note ATLAS-CONF-2018-055, CERN, Geneva, 2018.
  * [227] ATLAS Collaboration, “Measurement of the $b$-jet identification efficiency for high transverse momentum jets in $t\bar{t}$ events in the lepton + jets channel with the ATLAS detector using Run 2 data”, ATLAS Note ATL-PHYS-PUB-2021-004, CERN, Geneva, 2021.
  * [228] ATLAS Collaboration, “Measurement of the c-jet mistagging efficiency in $t\bar{t}$ events using pp collision data at $\sqrt{s}=13$ TeV collected with the ATLAS detector”,  Eur. Phys. J. C 82 (2022), no. 1, 95, doi:10.1140/epjc/s10052-021-09843-w, arXiv:2109.10627.
  * [229] ATLAS Collaboration, “Measurement of the $b$-jet identification efficiency with the $p_{\text{T}}^{\text{rel}}$ method in multi-jet events using pp collisions at $\sqrt{s}=13$ TeV with the ATLAS Detector”, ATLAS Note ATL-PHYS-PUB-2022-025, CERN, Geneva, 2022.
  * [230] ATLAS Collaboration, “Calibration of the light-flavour jet mistagging efficiency of the b-tagging algorithms with Z+jets events using 139 $\textrm{fb}^{-1}$ of ATLAS proton–proton collision data at $\sqrt{s}=13$ TeV”,  Eur. Phys. J. C 83 (2023) 728, doi:10.1140/epjc/s10052-023-11736-z, arXiv:2301.06319.
  * [231] I. Zurbano Fernandez et al., “High-Luminosity Large Hadron Collider (HL-LHC): Technical design report”, doi:10.23731/CYRM-2020-0010.
  * [232] D. Bertolini, P. Harris, M. Low, and N. Tran, “Pileup Per Particle Identification”,  JHEP 10 (2014) 059, doi:10.1007/JHEP10(2014)059, arXiv:1407.6013.
  * [233] P. T. Komiske, E. M. Metodiev, B. Nachman, and M. D. Schwartz, “Pileup Mitigation with Machine Learning (PUMML)”,  JHEP 12 (2017) 051, doi:10.1007/JHEP12(2017)051, arXiv:1707.08600.
  * [234] P. Hansen, J. W. Monk, and C. Wiglesworth, “A Wavelet Based Pile-Up Mitigation Method for the LHC Upgrade”, arXiv:1812.07412.
  * [235] J. Arjona Martínez et al., “Pileup mitigation at the Large Hadron Collider with graph neural networks”,  Eur. Phys. J. Plus 134 (2019) 333, doi:10.1140/epjp/i2019-12710-3, arXiv:1810.07988.
  * [236] S. Alipour-Fard, P. T. Komiske, E. M. Metodiev, and J. Thaler, “Pileup and Infrared Radiation Annihilation (PIRANHA): a paradigm for continuous jet grooming”,  JHEP 09 (2023) 157, doi:10.1007/JHEP09(2023)157, arXiv:2305.00989.
  * [237] ATLAS Collaboration, “Observation of $H\rightarrow b\bar{b}$ decays and $VH$ production with the ATLAS detector”,  Phys. Lett. B 786 (2018) 59–86, doi:10.1016/j.physletb.2018.09.013, arXiv:1808.08238.
  * [238] CMS Collaboration, “Observation of Higgs boson decay to bottom quarks”,  Phys. Rev. Lett. 121 (2018) 121801, doi:10.1103/PhysRevLett.121.121801, arXiv:1808.08242.
  * [239] CMS Collaboration, “Search for Higgs boson and observation of Z boson through their decay into a charm quark-antiquark pair in boosted topologies in proton-proton collisions at $\sqrt{s}$ = 13 TeV”,  Phys. Rev. Lett. 131 (2023) 041801, doi:10.1103/PhysRevLett.131.041801, arXiv:2211.14181.
  * [240] ATLAS Collaboration, “Direct constraint on the Higgs-charm coupling from a search for Higgs boson decays into charm quarks with the ATLAS detector”,  Eur. Phys. J. C 82 (2022) 717, doi:10.1140/epjc/s10052-022-10588-3, arXiv:2201.11428.
  * [241] ATLAS Collaboration, “Prospects for $H\rightarrow c\bar{c}$ using Charm Tagging with the ATLAS Experiment at the HL-LHC”, ATLAS PUB Note ATL-PHYS-PUB-2018-016, 2018.
  * [242] ATLAS Collaboration, “Extrapolation of ATLAS sensitivity to $H\rightarrow b\bar{b}$ and $H\rightarrow c\bar{c}$ decays in $VH$ production at the HL-LHC”, ATLAS PUB Note ATL-PHYS-PUB-2021-039, 2021.


11institutetext: Rochester Institute of Technology, NY, USA
11email<EMAIL_ADDRESS>22institutetext: West Virginia University
33institutetext: Qualcomm Inc

# Learning Transferable Object-Centric Diffeomorphic Transformations for Data
Augmentation in Medical Image Segmentation

Nilesh Kumar 11 Prashnna K. Gyawali 22 Sandesh Ghimire 33 Linwei Wang 11

###### Abstract

Obtaining labelled data in medical image segmentation is challenging due to
the need for pixel-level annotations by experts. Recent works have shown that
augmenting the object of interest with deformable transformations can help
mitigate this challenge. However, these transformations have been learned
globally for the image, limiting their transferability across datasets or
applicability in problems where image alignment is difficult. While object-
centric augmentations provide a great opportunity to overcome these issues,
existing works are only focused on position and random transformations without
considering shape variations of the objects. To this end, we propose a novel
object-centric data augmentation model that is able to learn the shape
variations for the objects of interest and augment the object in place without
modifying the rest of the image. We demonstrated its effectiveness in
improving kidney tumour segmentation when leveraging shape variations learned
both from within the same dataset and transferred from external datasets.

###### Keywords:

Data Augmentation Diffeomorphic transformations Image Segmentation

##  1 Introduction

A must-have ingredient for training a deep neural network (DNN) is a large
number of labelled data that is not always available in real-world
applications. This challenge of data annotation becomes even worse for medical
image segmentation tasks that require pixel-level annotation by experts. Data
augmentation (DA) is a recognized approach to tackle this challenge. Common DA
strategies create new samples by using predefined transformations such as
rotation, translation, and colour jitter to existing data, where the
performance gains heavily relies on the choice of augmentation operations and
parameters [1].

To mitigate this reliance, recent efforts have focused on learning optimal
augmentation operations for a given task and dataset [3, 15, 8, 11]. However,
transformations learned from these methods are typically still limited to a
predefined set of simple operations such as rotation, translation, and
scaling. In the meantime, another direction of research has emerged that
provides an alternative way of learning more expressive augmentations based on
deformation-based transformations commonly used in image registration [6, 16,
12]. Instead of pre-specifying a list of operations such as rotation and
scaling [3], these deformation-based transformations can describe more general
spatial transformations. Moreover, they are perfectly suited for modelling an
object’s shape changes [16] that are crucial for image segmentation tasks. It
thus provides an excellent candidate for learning shape variations of an
object from the data, and via which to enable shape-based augmentations for
medical image segmentation tasks. [16, 12].

However, to date, all existing approaches to learning deformable registration-
based DA assume a perfect alignment of image pairs to learn the
transformations. In other words, the deformation-based transformations are
learned globally for the image. This assumption is restrictive and associated
with several challenges. First, the learning of a global image-level
transformation requires image alignment that may be non-trivial in many
scenarios, such as the alignment of tumours that can appear at different
locations of an image, or alignment of images from different modalities. The
learning of transformations itself is also complicated by the presence of
other objects in the image and is best suited when the object of interest is
always in the same (and often centre) location in all the images, i.e., images
are globally aligned a priori [16]. Second, the application of the learned
global transformations for DA is also restricted to images similar (and
aligned) to those in training. It thus will be challenging to transfer the
learned shape variations to even the same objects across different locations,
orientations, or sizes in the image, let alone transferring across dataset
(e.g., to transfer the learned shape variations of an organ from one image
modality to another).

Intuitively, object-centric transformations and augmentations have the
potential to overcome the challenges associated with global image-level
transformations. Recently, an object-centric augmentation method termed as
TumorCP [13] showed that a simple object-level augmentation, via copy-pasting
a tumour from one location to another, can yield impressive performance gains.
However, the diversity of samples generated by TumorCP is limited to pasting
tumours on different backgrounds with random distortions without further
learned shape-based augmentation.

Similarly, other existing works on object-level augmentation of lesions have
mostly focused on position, orientation, and random transformations of the
lesion on different backgrounds [14, 17]. To date, no existing works have
considered shape-based object-centric augmentations. Enriching object-centric
DA with learned shape variations – a factor critical to object segmentation –
can result in more diverse samples and thereby improve DNN training for
medical image segmentation.

In this paper, we present a novel approach for learning and transferring
object-centric deformations for DA in medical image segmentation tasks. As
illustrated in Fig. 1, this is achieved with two key elements:

  * •

A generative model of object-centric deformations – constrained to C1
diffeomorphism for better DNN training – to describe shape variability learned
from paired patches of objects of interest. This allows the learning to focus
on the shape variations of an object regardless of its positions and sizes in
the image, thus bypassing the requirement for image alignment.

  * •

An online augmentation strategy to sample transformations from the generative
model and to augment the objects of interest in place without distorting the
surrounding content in the image. This allows us to add shape diversity to the
objects of interest in an image regardless of their positions or sizes,
eventually facilitating transferring the learned variations across datasets.

Figure 1: Overview of the presented approach. a) Learning a generative model
describing object-centric shape variations as diffeomorphic transformations.
b) Sampling transformations from the learned generative model and deforming an
object in place (highlighted with a red square) without distorting the
surrounding content in the image.

We demonstrated the effectiveness of the presented object-centric
diffeomorphic augmentation in kidney tumour segmentation, including using
shape variations of kidney tumours learned from the same dataset (KiTS [7]),
as well as transferring those learned from a larger liver tumour dataset (LiTS
[2]). Experimental results showed that it can enrich the augmentation
diversity of other techniques such as TumorCP [13], and improve kidney tumour
segmentation [7] using shape variations learned either within or outside the
same training data.

##  2 Methods

We focus on DA for tumour segmentation because tumours can occur at different
locations of an organ with substantially different orientations and sizes. It
thus presents a challenging scenario where global image-level deformable
transformations cannot apply. mentation approach comprises as outlined in
Below we describe the two key methodological elements.

###  2.1 Object-Centric Diffeomorphism as a Generative Model

The goal of this element is to learn to generate diffeomorphic transformation
parameters $\theta$ that describe shape variations – in the form of deformable
transformations $T^{\theta}$ – that are present within training instances of
tumour $x$. To realize this, we train a generative model $G(.)$ for $\theta$
such that, when given two instances of tumours ($x_{src},x_{tgt}$), it is
asked to generate $\theta$ from the encoded latent representations $z$ in
order to deform $x_{src}$ through $T^{\theta}(x_{src})$ to $x_{tgt}$.

####  2.1.1 Transformations:

In order to model shape deformations between $x_{src}$ and $x_{tgt}$, we need
highly expressive transformations to capture rich shape variations in tumour
pairs. We assume a spatial transformation $T^{\theta}$ in the form of pixel-
wise displacement field $u$ as $T^{\theta}(x)=x+u$. Inspired from [4, 6], we
turn to $C^{1}$ diffeomorphisms to model our transformations. $C^{1}$
diffeomorphisms are smooth and invertible transformations that preserve
differentiability up to the first derivative, making them a suitable choice to
be embedded in a neural network for gradient-based optimization [4]. However,
the set of all diffeomorphisms is an infinitely large Lie group. To overcome
this issue, we focus on a specific finite-dimensional subset of the Lie group
that is large enough to capture the relevant variations in the tumours. For
this, we make use of continuous piecewise-affine-based (CPAB) transformation
based on the integration of CPA velocity field $v^{\theta}$ proposed in [5].
Let $\Omega$ $\subset$ $R^{2}$ denote the tumour domain and let $P$ be
triangular tesselation of $\Omega$ [6]. A velocity field that maps points from
$\Omega$ to $R^{2}$ is said to be piecewise affine (PA) if it is affine when
restricted to each triangle of $P$. The set $V$ of $v^{\theta}$ which are zero
on the boundary of $\Omega$ can be shown to be finite-dimensional linear space
[5]. The dimensionality $d$ of $V$ is a result of how fine $P$ is tessellated.
It can be shown that $V$ is parameterized by $\theta$, i.e., any instance of
$V$ is a linear combination of $d$ orthonormal CPA fields with weights
$\theta$ [5]. A spatial transformation $T^{\theta}$ can be derived by
integrating a velocity field $v^{\theta}$ [5] as:

$u^{\theta}(x,t)=x+\int_{0}^{t}v^{\theta}(u^{\theta}(x,t))dt$ (1)

where the integration can be done via a specialized solver [5]. The solver
chosen produces faster and more accurate results than a generic ODE solver.
Specifically, the cost for this solver is $O(C1)+O(C2$ x Number of integration
steps), where $C1$ is matrix exponential for the number of cells an image is
divided into and $C2$ is the dimensionality of an image. The transformations
$T^{\theta}$ thus can be described by a generative model of $\theta$. We also
experimented with squaring and scaling layers for integration but that
resulted in texture loss when learning transformations.

####  2.1.2 Generative Modeling:

The data generation process can be described as:

$\displaystyle p(z)\sim\mathcal{N}(0,I),\quad\theta\sim
p_{\phi}(\theta|z),\quad x_{tgt}\sim p(x_{tgt}|\theta,x_{src})$ (2)
$\displaystyle
p(x_{tgt},z|x_{src})=p(z)\int_{\theta}p(x_{tgt}|\theta,x_{src})p_{\phi}(\theta|z)d\theta=p(z)p_{\phi}(x_{tgt}|z,x_{src})$
(3)

where $z$ is the latent variable assumed to follow an isotropic Gaussian
prior, $p_{\phi}(\theta|z)$ is modeled by a neural network parameterized by
$\phi$, and $p(x_{tgt}|\theta,x_{src})$ follows the deformable transformation
as described in Equation (1).

We define variational approximations of the posterior density as
$q_{\psi}(z|x_{src},x_{tgt})$, modeled by a convolutional neural network that
expects two inputs $x_{src}$ and $x_{tgt}$. Passing a tuple of $x_{src}$ and
$x_{tgt}$ as the input helps the latent representations to learn the spatial
difference between two tumour samples. Alternatively, the generative model as
described can be considered as a conditional model where both the generative
and inference model is conditioned on the source tumour sample $x_{src}$.

####  2.1.3 Variational Inference:

The parameters $\psi$ and $\phi$ are optimized by the modified evidence lower
bound (ELBO) of the log-likelihood $\log p(x_{tgt}|x_{src})$:

$\begin{split}{}\log
p(x_{tgt}|x_{src})\geq\mathcal{L}_{ELBO}=E_{q_{\psi}(z|x_{src},x_{tgt})}p_{\phi}(x_{tgt}|z,x_{src})\\\
-\beta{D}_{KL}(q_{\psi}(z|x_{src},x_{tgt})||p(z))\end{split}$ (4)

where the first term in the ELBO takes the form of similarity loss: $L_{2}$
norm on the difference between $x_{tgt}$ and
$\hat{x}_{src}=T^{\theta}(x_{src})$ synthesized using the $\theta$ from
$G(z)$.

The second KL term constrains our approximated posterior
$q_{\psi}(z|x_{src},x_{tgt})$ to be closer to the isotropic Gaussian prior
$p(z)$, and its contribution to the overall loss is scaled by the
hyperparameter $\beta$. To further ensure that $\hat{x}_{src}$ looks
realistic, we discourage $G(z)$ from generating overly-expressive
transformations by adding a regularization term over the $L_{2}$ norm of the
displacement field $u$ with a tunable hyperparameter $\lambda_{reg}$. The
final objective function becomes:

$\mathcal{L}=\mathcal{L}_{ELBO}+\lambda_{reg}*\|u\|_{2}$ (5)

####  2.1.4 Object-Centric Learning:

To learn object-centric spatial transformations, $x_{src}$ and $x_{tgt}$ are
in the forms of image patches that solely contain tumours. Given an image and
its corresponding tumour segmentation mask ($X,Y$), we first extract a
bounding box around the tumour by applying skimage.measure.regionprops from
the scikit-image package to $Y$. We then use this bounding box to carve out
the tumour $x$ from the image $X$, masking out all the regions within the
bounding box that do not belong to the tumour. All the tumour patches are then
resized to the same scale, such that tumours of different sizes can be
described by the same tesselation resolution. When pairing tumour patches, we
pair each tumour with its $K$ nearest neighbour tumours based on their
Euclidean distance – this again avoids learning overly expressive
transformation when attempting to deform between significantly different
tumour shapes.

###  2.2 Online Augmentations with Generative Models

The goal of this element is to sample random object-centric transformations of
$T^{\theta}$ from $G(z)$, to generate diverse augmentations of different
instances of tumours in place. However, if we only transform the tumour and
keep the rest of the image identical, the transformed tumour may appear
unrealistic and out of place. To ensure that the entire transformed image
appears smooth, we use a hybrid strategy to construct a deformation field for
the entire image $X$ that combines tumour-specific deformations with an
identity transform for the rest of the image. Specifically, we fill a small
region around the tumour with displacements of diminishing magnitudes,
achieved by propagating the deformations from the boundaries of the
deformation fields from $G(z)$ to their neighbours with reduced magnitudes.
Repeating this process ensures that the change at the boundaries is smooth and
that the transformed region appears naturally as part of the image.

##  3 Experiments and Results

We used two publicly available datasets, LiTS [2] and KiTS [7], for our
experiments. LiTS [7] contains liver and liver tumour segmentation masks for
200 scans in total, 130 train and 70 test. Similarly, KiTS [2] has kidney and
kidney tumour segmentation masks for 300 scans, 168 train, 42 validation, and
90 test. We trained our generative model $G(z)$ on KiTS and LiTS separately to
learn spatial variations in tumour shapes. We then used either of the learned
transformation to augment kidney tumor segmentation tasks on subsets of KiTS
data with varying sizes. Code link:
https://github.com/nileshkumar0726/Learning_Transformations

###  3.1 Generative Model Implementation, Training, and Evaluation

Figure 2: Visual examples of the generative model in (a) reconstructing
$x_{tgt}$ given pairs of $x_{scr}$ and $x_{tgt}$, and (b) generating deformed
samples given a single $x_{src}$.

####  3.1.1 Data:

We prepared data for the generative model $G(z)$ training by first carving out
tumour regions from individual slices of 3D scans using tumour segmentation
masks. All tumour patches were resized to 30$\times$30, and each was paired
with eight of its closest neighbours. We trained $G(z)$ with different sizes
of data for individual experiments presented in Table 1, ranging from using
11000 pairs from LiTS to only 3000 pairs when using only 25% samples from
KiTS.

####  3.1.2 Model:

The encoder of $G(z)$ consisted of five convolutional layers and three fully
connected layers, with a latent dimension of 12 for $z$. The decoder consisted
of five fully connected layers to output the parameters $\theta$ for
$T^{\theta}$. We trained the $G(z)$ for a total of 400 epochs and a batch size
of 16. We also implemented early stopping if the validation loss does not
improve for 20 epochs. We used Adam optimizer [10] with a learning rate of
1e-4.

We trained separate $G(z)$’s from KiTS and LiTS, respectively. We set $\beta$
= 0.001 for both models but needed a high $\lambda_{reg}$ of 0.009 for the
LiTS model compared to 0.004 for KiTS model. The tumours in the LiTS have
higher intensity differences, which may explain why a higher value of
$\lambda_{reg}$ was needed to ensure that transformed tumours did not become
unrealistic.

####  3.1.3 Results:

We evaluated $G(z)$ with two criteria. First, the model needs to be able to
reconstruct $x_{tgt}$ by generating $\theta$ to transform $x_{src}$. Second,
the model needs to be able to generate diverse transformed tumour samples for
a given tumour sample. Fig. 2 presents visual examples of the reconstruction
and generation results achieved by $G(z)$. It can be observed that the
reconstruction is successful in most cases, except when $x_{src}$ and
$x_{tgt}$ were too different. This was necessary to ensure that
$T^{\theta}(x_{src})$ did not produce unrealistic examples. The averaged
L2-loss of transformed $\hat{x}_{src}$ was 1.23 on the validation pairs. We
also visually inspected validation samples after training to make sure that
the deformed tumours were similar to the original tumours in appearance. The
generated examples of tumours from a single source, as shown in Fig. 2(b),
demonstrated that the generations were diverse yet realistic.

###  3.2 Deformation-Based DA for Kidney Tumour Segmentation

% data for training | Augmentations | Mean Dice (std)* $\uparrow{}$ |
---|---|---|---
25% | Baseline | 0.467 (0.014) |
Random Wrapping | 0.535 (0.003) |
TumorCP | 0.568 (0.014) |
Diffeo (within-data | cross-data) | 0.497 (0.006) | 0.505 (0.002) |
| TumorCP + Diffeo (within-data | cross-data) |  0.581 (0.012) | 0.576 (0.015) |
50% | Baseline | 0.608 (0.017) |
Random Wrapping | 0.6675 (0.0091) |
TumorCP | 0.669 (0.011) |
Diffeo (within-data | cross-data) | 0.640 (0.002) | 0.639 (0.014) |
| TumorCP + Diffeo (within-data | cross-data) | 0.689 (0.013) | 0.702 (0.016) |
75% | Baseline | 0.656 (0.027) |
Random Wrapping | 0.6774 (0.0036) |
TumorCP | 0.690 (0.003 |
Diffeo (within-data | cross-data) | 0.662 (0.006) | 0.655 (0.001) |
| TumorCP + Diffeo (within-data | cross-data) | 0.707 (0.001) | 0.718 (0.007) |
100% | Baseline | 0.680 (0.025) |
Random Wrapping | 0.6698 (0.016) |
TumorCP | 0.702 (0.005) |
Diffeo (within-data | cross-data) | 0.687 (0.014) | 0.688 (0.028) |
| TumorCP + Diffeo (within-data | cross-data) | 0.709 (0.004) | 0.713 (0.019) |

Table 1: KiTS segmentation results in terms of DICE score. The baseline model
already includes standard data augmentations. Within-data augmentations used
transformations learned from KiTS using the same % of training data for
segmentation tasks. Cross-data augmentations used transformations learned from
LiTS. TumorCP was also always performed within data.

####  3.2.1 Data:

We then used $G(z)$ to generate deformation-based augmentations to increase
the size and diversity of training samples for kidney tumour segmentation on
KiTS. To assess the effect of augmentations on different sizes of labelled
data, we considered training using 25%, 50%, 75%, and 100% of the KiTS
training set. We considered two DA scenarios: augment with transformations
learned from KiTS (within-data augmentation) versus from LiTS (cross-data
augmentation).

####  3.2.2 Models:

For the base segmentation network, we adopted nnU-net [9] as it contains state
of the art (SOTA) pipeline for medical image segmentation on most datasets. To
make the segmentation pipeline compatible with $G(z)$, we used the 2D
segmentation module of nnU-net. For baselines, we considered 1) default
augmentations such as rotation, scaling, and random crop in nnU-net as well as
2) TumorCP, all modified for 2D segmentation. Note that our goal is not to
achieve SOTA results on KiTS, but to test the relative efficacy of the
presented DA strategies in comparison with existing object-centric DA methods.

####  3.2.3 Results:

We use Sørensen-Dice Coefficient (Dice) to measure segmentation network
performance. Dice measures the overlap between prediction and ground truth. As
summarized in Table 1, when combined with TumorCP, the presented augmentations
were able to generate statistically significant (paired t-test, $p\leq 0.05$)
improvements in all cases compared to TumorCP alone. This demonstrated the
benefit of enriching simple copy-and-paste DA with shape variations.
Interestingly, cross-data transferring of the learned augmentations (from
LiTS) outperformed the within-data augmentation in the majority of the cases.
Which we believe is because of two factors. Firstly, learning of the within-
data augmentations is limited to the percentage of the training set used for
segmentation. The number of objects to learn transformations from is thus
greater in cross-data augmentation settings. Secondly, the transformations
present in cross-data are completely unseen in the segmentation training
network which helps in generating more diverse samples. Note that, as the
transformations are learned as variations in object shapes, they can be
transferred easily across datasets

Surprisingly, the improvements achieved by the presented augmentation strategy
were the most prominent when the segmentation was trained on 50% and 75% of
the KiTS training set. This is contrary to the expectation that DA would be
most beneficial when the labelled training set is small. This may be because
smaller sample sizes do not provide sufficient initial tumor samples for shape
transformations. This may also explain why the combination of TumorCP boosted
the performance of our augmentation strategy, as the oversampling nature of
TumorCP provided more tumour samples for the presented strategy to transform
to further enrich the training set. It is also worth noting that in contrast
to prior literature, random wrapping of objects does not come close to the
learned augmentations. We speculate that while unrealistic transformations
work for whole images, they may be problematic when only augmenting specific
local objects in an image.

##  4 Discussion and Conclusions

In this work, we presented a novel diffeomorphism-based object-centric
augmentation that can be learned and used to augment the objects of interest
regardless of their position and size in an image. As demonstrated by the
experimental results, this allows us to not only introduce new variations to
unfixed objects like tumours in an image but also transfer the knowledge of
shape variations across datasets. An immediate next step will be to extend the
presented approach to learn and transfer 3D transformations for 3D
segmentation tasks, and to enrich the shape-based transformation with
appearance-based transformations. In the long term, it would be interesting to
explore ways to transfer knowledge about more general forms of variations
across datasets.

##  5 Acknowledgments

This work is supported by the National Institute of Nursing Research (NINR) of
the National Institutes of Health (NIH) under Award Number R01NR018301.

## References

  * [1] Alexey, D., Fischer, P., Tobias, J., Springenberg, M.R., Brox, T.: Discriminative unsupervised feature learning with exemplar convolutional neural networks. IEEE Trans. Pattern Analysis and Machine Intelligence 99 (2015)
  * [2] Bilic, P., Christ, P., Li, H.B., Vorontsov, E., Ben-Cohen, A., Kaissis, G., Szeskin, A., Jacobs, C., Mamani, G.E.H., Chartrand, G., Lohöfer, F., Holch, J.W., Sommer, W., Hofmann, F., Hostettler, A., Lev-Cohain, N., Drozdzal, M., Amitai, M.M., Vivanti, R., Sosna, J., Ezhov, I., Sekuboyina, A., Navarro, F., Kofler, F., Paetzold, J.C., Shit, S., Hu, X., Lipková, J., Rempfler, M., Piraud, M., Kirschke, J., Wiestler, B., Zhang, Z., Hülsemeyer, C., Beetz, M., Ettlinger, F., Antonelli, M., Bae, W., Bellver, M., Bi, L., Chen, H., Chlebus, G., Dam, E.B., Dou, Q., Fu, C.W., Georgescu, B., i Nieto, X.G., Gruen, F., Han, X., Heng, P.A., Hesser, J., Moltz, J.H., Igel, C., Isensee, F., Jäger, P., Jia, F., Kaluva, K.C., Khened, M., Kim, I., Kim, J.H., Kim, S., Kohl, S., Konopczynski, T., Kori, A., Krishnamurthi, G., Li, F., Li, H., Li, J., Li, X., Lowengrub, J., Ma, J., Maier-Hein, K., Maninis, K.K., Meine, H., Merhof, D., Pai, A., Perslev, M., Petersen, J., Pont-Tuset, J., Qi, J., Qi, X., Rippel, O., Roth, K., Sarasua, I., Schenk, A., Shen, Z., Torres, J., Wachinger, C., Wang, C., Weninger, L., Wu, J., Xu, D., Yang, X., Yu, S.C.H., Yuan, Y., Yue, M., Zhang, L., Cardoso, J., Bakas, S., Braren, R., Heinemann, V., Pal, C., Tang, A., Kadoury, S., Soler, L., van Ginneken, B., Greenspan, H., Joskowicz, L., Menze, B.: The liver tumor segmentation benchmark (lits). Medical Image Analysis 84, 102680 (2023). https://doi.org/https://doi.org/10.1016/j.media.2022.102680, https://www.sciencedirect.com/science/article/pii/S1361841522003085
  * [3] Cubuk, E.D., Zoph, B., Mane, D., Vasudevan, V., Le, Q.V.: Autoaugment: Learning augmentation strategies from data. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 113–123 (2019)
  * [4] Detlefsen, N.S., Freifeld, O., Hauberg, S.: Deep diffeomorphic transformer networks. In: 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 4403–4412 (2018). https://doi.org/10.1109/CVPR.2018.00463
  * [5] Freifeld, O., Hauberg, S., Batmanghelich, K., Fisher, J.W.: Highly-expressive spaces of well-behaved transformations: Keeping it simple. In: 2015 IEEE International Conference on Computer Vision (ICCV). pp. 2911–2919 (2015). https://doi.org/10.1109/ICCV.2015.333
  * [6] Hauberg, S., Freifeld, O., Larsen, A.B.L., Fisher, J., Hansen, L.: Dreaming more data: Class-dependent distributions over diffeomorphisms for learned data augmentation. In: Artificial Intelligence and Statistics. pp. 342–350 (2016)
  * [7] Heller, N., Sathianathen, N., Kalapara, A., Walczak, E., Moore, K., Kaluzniak, H., Rosenberg, J., Blake, P., Rengel, Z., Oestreich, M., Dean, J., Tradewell, M., Shah, A., Tejpaul, R., Edgerton, Z., Peterson, M., Raza, S., Regmi, S., Papanikolopoulos, N., Weight, C.: The kits19 challenge data: 300 kidney tumor cases with clinical context, ct semantic segmentations, and surgical outcomes (2019). https://doi.org/10.48550/ARXIV.1904.00445, https://arxiv.org/abs/1904.00445
  * [8] Ho, D., Liang, E., Stoica, I., Abbeel, P., Chen, X.: Population based augmentation: Efficient learning of augmentation policy schedules. arXiv preprint arXiv:1905.05393 (2019)
  * [9] Isensee, F., Jaeger, P.F., Kohl, S.A., Petersen, J., Maier-Hein, K.H.: nnu-net: a self-configuring method for deep learning-based biomedical image segmentation. Nature methods 18(2), 203–211 (2021)
  * [10] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization (2014). https://doi.org/10.48550/ARXIV.1412.6980, https://arxiv.org/abs/1412.6980
  * [11] Lim, S., Kim, I., Kim, T., Kim, C., Kim, S.: Fast autoaugment. In: Advances in Neural Information Processing Systems. pp. 6662–6672 (2019)
  * [12] Shen, Z., Xu, Z., Olut, S., Niethammer, M.: Anatomical data augmentation via fluid-based image registration. In: Martel, A.L., Abolmaesumi, P., Stoyanov, D., Mateus, D., Zuluaga, M.A., Zhou, S.K., Racoceanu, D., Joskowicz, L. (eds.) Medical Image Computing and Computer Assisted Intervention – MICCAI 2020\. pp. 318–328. Springer International Publishing, Cham (2020)
  * [13] Yang, J., Zhang, Y., Liang, Y., Zhang, Y., He, L., He, Z.: Tumorcp: A simple but effective object-level data augmentation for tumor segmentation. In: de Bruijne, M., Cattin, P.C., Cotin, S., Padoy, N., Speidel, S., Zheng, Y., Essert, C. (eds.) Medical Image Computing and Computer Assisted Intervention – MICCAI 2021. pp. 579–588. Springer International Publishing, Cham (2021)
  * [14] Zhang, X., Liu, C., Ou, N., Zeng, X., Xiong, X., Yu, Y., Liu, Z., Ye, C.: Carvemix: A simple data augmentation method for brain lesion segmentation. In: de Bruijne, M., Cattin, P.C., Cotin, S., Padoy, N., Speidel, S., Zheng, Y., Essert, C. (eds.) Medical Image Computing and Computer Assisted Intervention – MICCAI 2021. pp. 196–205. Springer International Publishing, Cham (2021)
  * [15] Zhang, X., Wang, Q., Zhang, J., Zhong, Z.: Adversarial autoaugment. In: International Conference on Learning Representations (2020), https://openreview.net/forum?id=ByxdUySKvS
  * [16] Zhao, A., Balakrishnan, G., Durand, F., Guttag, J.V., Dalca, A.V.: Data augmentation using learned transformations for one-shot medical image segmentation. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) (June 2019)
  * [17] Zhu, Q., Wang, Y., Yin, L., Yang, J., Liao, F., Li, S.: Selfmix: A self-adaptive data augmentation method for lesion segmentation. In: Wang, L., Dou, Q., Fletcher, P.T., Speidel, S., Li, S. (eds.) Medical Image Computing and Computer Assisted Intervention – MICCAI 2022. pp. 683–692. Springer Nature Switzerland, Cham (2022)


# On $k$-rainbow domination in middle graphs

Kijung Kim  Department of Mathematics, Pusan National University, Busan 46241,
Republic of Korea<EMAIL_ADDRESS>
###### Abstract.

Let $G$ be a finite simple graph with vertex set $V(G)$ and edge set $E(G)$. A
function $f:V(G)\rightarrow\mathcal{P}(\\{1,2,\dotsc,k\\})$ is a $k$-rainbow
dominating function on $G$ if for each vertex $v\in V(G)$ for which
$f(v)=\emptyset$, it holds that $\bigcup_{u\in N(v)}f(u)=\\{1,2,\dotsc,k\\}$.
The weight of a $k$-rainbow dominating function is the value $\sum_{v\in
V(G)}|f(v)|$. The $k$-rainbow domination number $\gamma_{rk}(G)$ is the
minimum weight of a $k$-rainbow dominating function on $G$. In this paper, we
initiate the study of $k$-rainbow domination numbers in middle graphs. We
define the concept of a middle $k$-rainbow dominating function, obtain some
bounds related to it and determine the middle $3$-rainbow domination number of
some classes of graphs. We also provide upper and lower bounds for the middle
$3$-rainbow domination number of trees in terms of the matching number. In
addition, we determine the $3$-rainbow domatic number for the middle graph of
paths and cycles.

Key words: $k$-rainbow domination number, middle graph, middle $k$-rainbow
domination number, matching number, $k$-rainbow domatic number

###### 2010 Mathematics Subject Classification:

05C69

This research was supported by Basic Science Research Program through the
National Research Foundation of Korea funded by the Ministry of Education
(2020R1I1A1A01055403).

##  1\. Introduction

Let $G=(V,E)$ be a connected undirected graph with the vertex set $V=V(G)$ and
edge set $E=E(G)$. The order of $G$ is defined as the cardinality of $V$. The
open neighborhood of $v\in V(G)$ is the set $N(v)=\\{u\in V(G)\mid uv\in
E(G)\\}$ and the closed neighborhood of $v\in V(G)$ is the set
$N[v]:=N(v)\cup\\{v\\}$. The degree of $v\in V(G)$ is defined as the
cardinality of $N(v)$, denoted by $deg_{G}(v)$. When no confusion arises, we
may delete the subscript $G$ in $deg_{G}(v)$. The maximum degree and minimum
degree of $G$ are denoted by $\Delta(G)$ and $\delta(G)$, respectively We
write $P_{n}$, $C_{n}$ and $K_{n}$ for a path, a cycle and a complete graph,
respectively.

In [8], Hamada and Yoshimura defined the middle graph of a graph. The middle
graph $M(G)$ of a graph $G$ is the graph obtained by subdividing each edge of
$G$ exactly once and joining all these newly introduced vertices of adjacent
edges of $G$. The precise definition of $M(G)$ is as follows. The vertex set
$V(M(G))$ is $V(G)\cup E(G)$. Two vertices $v,w\in V(M(G))$ are adjacent in
$M(G)$ if (i) $v,w\in E(G)$ and $v,w$ are adjacent in $G$ or (ii) $v\in V(G)$,
$w\in E(G)$ and $v,w$ are incident in $G$.

In the graph domination, a set of vertices is selected as guards such that
each vertex not selected has a guard as a neighbor. As a generalization of the
graph domination, Bre$\acute{s}$ar et al. introduced the concept of rainbow
domination in [3]. In the $k$-rainbow domination, $k$-different types of
guards are required in the neighborhood of a non-selected vertex. Let $[k]$ be
the set of positive integers at most $k$. A function
$f:V(G)\rightarrow\mathcal{P}([k])$ is a $k$-rainbow dominating function on
$G$ if for each vertex $v\in V(G)$ for which $f(v)=\emptyset$, it holds that
$\bigcup_{u\in N(v)}f(u)=[k]$. The weight of a $k$-rainbow dominating function
is the value $\sum_{v\in V(G)}|f(v)|$. The $k$-rainbow domination number
$\gamma_{rk}(G)$ is the minimum weight of a $k$-rainbow dominating function on
$G$. In [4], Chang et al. proved that the $k$-rainbow domination is NP-
complete. So, it is worthwhile to determine the $k$-rainbow domination numbers
of some classes of graphs. Indeed, there are many papers on the $2$-rainbow
domination. The latest survey of the $2$-rainbow domination is introduced in
[2]. For $k\geq 3$, it is more difficult to determine the $k$-rainbow
domination number of a graph. The following are a few results on the
$3$-rainbow domination number. In [10], Shao et al. determined the $3$-rainbow
domination numbers of paths, cycles and generalized Petersen graphs $P(n,1)$.
In [12], Wang et al. determined the $3$-rainbow domination number of
$P_{3}\square P_{n}$. In [7], Gao et al. determined the $3$-rainbow domination
numbers of $C_{3}\square C_{m}$ and $C_{4}\square C_{m}$. In [5], Cynthia et
al. determined the $3$-rainbow domination number of circulant graph
$G(n;\pm\\{1,2,3\\})$. In [6], Furuya et al. proved that for every connected
graph $G$ of order $n\geq 8$ with $\delta(G)\geq 2$,
$\gamma_{r3}(G)\leq\frac{5n}{6}$.

To study the $k$-rainbow domination number in the class of middle graphs, we
define the following concept. For $v\in V(G)$, we denote $\\{e\in E(G)\mid
e~{}\text{is incident with}~{}v\\}$ by $N_{M}(v)$. For $e\in E(G)$, we denote
$\\{x\in V(G)\cup E(G)\mid x~{}\text{is either adjacent or incident
with}~{}e\\}$ by $N_{M}(e)$. We write $N_{M}[x]=N_{M}(x)\cup\\{x\\}$. A middle
$k$-rainbow dominating function (MkRDF) on a graph $G$ is a function $f:V\cup
E\rightarrow\mathcal{P}([k])$ such that every element $x\in V\cup E$ for which
$f(x)=\emptyset$ satisfies $\bigcup_{v\in N_{M}(x)}f(v)=[k]$. A middle
$k$-rainbow dominating function $f$ gives an ordered partition $(V_{0}\cup
E_{0},V_{1}\cup E_{1},V_{2}\cup E_{2},\dotsc,V_{k}\cup E_{k})$, where
$V_{i}:=\\{x\in V\mid|f(x)|=i\\}$ and $E_{i}:=\\{x\in E\mid|f(x)|=i\\}$. The
weight of a middle $k$-rainbow dominating function $f$ is
$\omega(f):=\sum_{x\in V\cup E}|f(x)|$. The middle $k$-rainbow domination
number $\gamma_{rk}^{\star}(G)$ of $G$ is the minimum weight of a middle
$k$-rainbow dominating function of $G$. A $\gamma_{rk}^{\star}(G)$-function is
a MkRDF on $G$ with weight $\gamma_{rk}^{\star}(G)$. We remark that
$\gamma_{rk}^{\star}(G)=\gamma_{rk}(M(G))$ for any graph $G$. In [9], it was
considered only $2$-rainbow domination numbers of the middle graphs. In this
paper, we initiate the study of the middle $k$-rainbow domination in graphs.
In particular, we determine the exact value of middle $3$-rainbow domination
numbers of some classes of graphs. A matching in a graph $G$ is a set of
pairwise nonadjacent edges. The maximum number of edges in a matching of a
graph $G$ is called the matching number of $G$ and denoted by
$\alpha^{\prime}(G)$. We provide upper and lower bounds for the middle
$3$-rainbow domination number of trees in terms of the matching number. A set
$\\{f_{1},\dotsc,f_{d}\\}$ of $k$-rainbow dominating functions of $G$ is
called a $k$-rainbow dominating family on $G$ if $\sum_{i=1}^{d}|f_{i}(v)|\leq
k$ for each $v\in V(G)$. The maximum number of functions in a $k$-rainbow
dominating family on $G$ is the $k$-rainbow domatic number of $G$, denoted by
$d_{rk}(G)$. It is known that $k$-rainbow domatic number is well-defined and
$d_{rk}(G)\geq k$ for every graph $G$ (See [11]). We determine the $3$-rainbow
domatic number for the middle graph of paths and cycles.

The rest of this section, we present some necessary terminology and notation.
For terminology and notation on graph theory not given here, the reader is
referred to [1]. Let $T$ be a (rooted) tree. A leaf of $T$ is a vertex of
degree one. A pendant edge is an edge incident with a leaf. A support vertex
is a vertex adjacent to a leaf. For a vertex $v$, $C(v)$ denote the set of the
children of $v$. $D[v]$ denote the set of the descendants and $v$. The subtree
induced by $D[v]$ is denoted by $T_{v}$. We write $K_{1,n-1}$ for the star of
order $n\geq 3$. The double star $DS_{p,q}$, where $p,q\geq 1$, is the graph
obtained by joining the centers of two stars $K_{1,p}$ and $K_{1,q}$. A
healthy spider $S_{t,t}$ is the graph from a star $K_{1,t}$ by subdividing
each edges of $K_{1,t}$. A wounded spider $S_{t,r}$ is the graph from a star
$K_{1,t}$ by subdividing $r$ edges of $K_{1,t}$, where $r\leq t-1$. Note that
a star $K_{1,t}$ is a wounded spider $S_{t,0}$. For a graph $G$ and its subset
$S$, $G-S$ denotes the subgraph of $G$ induced by $V(G)\setminus V(S)$. A
diametral path of $G$ is a path with the length which equals the diameter of
$G$. The complement of $G=(V,E)$ is the graph $(V,\overline{E})$, which is
denoted by $\overline{G}$, where $uv\in\overline{E}$ if and only if $uv\not\in
E$.

##  2\. General bounds of the middle $k$-rainbow domination number

In this section, we obtain general bounds of the middle $k$-rainbow domination
number. First, we begin by giving a simple lower bound on the middle
$k$-rainbow domination number.

######  Observation 2.1.

If $G$ is a graph with $|V(G)|+|E(G)|\geq k$, then $\gamma_{rk}^{\star}(G)\geq
k$.

###### Proof.

Let $f$ be a $\gamma_{rk}^{\star}(G)$-function. If $f(x)=\emptyset$ for some
$x\in V(G)\cup E(G)$, then clearly $\bigcup_{y\in
N_{M}(x)}f(y)=\\{1,\dotsc,k\\}$. If $f(x)\neq\emptyset$ for all $x\in V(G)\cup
E(G)$, then it follows from $|V(G)|+|E(G)|\geq k$ that
$\gamma_{rk}^{\star}(G)\geq k$. ∎

######  Proposition 2.2.

Let $G$ be a graph of order $n\geq 2$. Then $\gamma_{r3}^{\star}(G)=3$ if and
only if $G\in\\{\overline{K_{3}},P_{2}\\}$.

###### Proof.

If $G\in\\{\overline{K_{3}},P_{2}\\}$, then clearly
$\gamma_{r3}^{\star}(G)=3$. Conversely, assume that $\gamma_{r3}^{\star}(G)=3$
and let $f$ be a $\gamma_{r3}^{\star}(G)$-function. If there exists $x\in
V(G)\cup E(G)$ such that $f(x)=[3]$, then $x\in E(G)$ for otherwise $x$ can
not dominate the other vertices. Thus, $G=P_{2}$.

Now assume that there is no element with weight $3$. If $f(v)=\emptyset$ for
some $v\in V(G)$, then there exist at least two edges $e_{1},e_{2}$ incident
to $v$ such that $f(e_{1})$ and $f(e_{2})$ are not empty. But, end vertices of
$e_{1},e_{2}$ except for $v$ are not dominated, a contradiction. Thus, every
vertex in $V(G)$ has non-zero weight so that there are at most three vertices
in the graph $G$. One can easily check that $G=\overline{K_{3}}$ or $P_{2}$. ∎

######  Theorem 2.3.

If $G$ is a graph and $v\in V(G)$, then
$\gamma_{rk}^{\star}(G)-\text{min}\\{\Delta(G)+1,k\\}\leq\gamma_{rk}^{\star}(G-v)\leq\gamma_{rk}^{\star}(G)$.

###### Proof.

First, we claim that
$\gamma_{rk}^{\star}(G)-\text{min}\\{\Delta(G)+1,k\\}\leq\gamma_{rk}^{\star}(G-v)$.
Let $f$ be a $\gamma_{rk}^{\star}(G-v)$-function. If $k\leq\Delta(G)+1$, then
define $g:V(G)\cup E(G)\rightarrow\mathcal{P}([k])$ by $g(v)=[k]$,
$g(x)=\emptyset$ for $x\in N_{M}(v)$ and $g(x)=f(x)$ otherwise. If
$k>\Delta(G)+1$, then define $g:V(G)\cup E(G)\rightarrow\mathcal{P}([k])$ by
$g(x)=\\{1\\}$ for each $x\in N_{M}[v]$ and $g(x)=f(x)$ otherwise. Clearly,
$g$ is a MkRDF of $G$ with weight at most $\gamma_{rk}^{\star}(G-v)$ \+
min$\\{\Delta(G)+1,k\\}$. Thus,
$\gamma_{rk}^{\star}(G)-\text{min}\\{\Delta(G)+1,k\\}\leq\gamma_{rk}^{\star}(G-v)$.

Next, we claim that $\gamma_{rk}^{\star}(G-v)\leq\gamma_{rk}^{\star}(G)$. Let
$f$ be a $\gamma_{rk}^{\star}(G)$-function. Define $h:V(G-v)\cup
E(G-v)\rightarrow\mathcal{P}([k])$ by $h(u)=f(u)\cup f(uv)$ for $u\in N(v)$
and $h(x)=f(x)$ otherwise. Then clearly $h$ is a MkRDF of $G-v$ with weight
$\gamma_{rk}^{\star}(G)$. ∎

######  Theorem 2.4.

Let $G$ be a graph. Then

  1. (i)

$\gamma_{rk}^{\star}(G)-k\leq\gamma_{rk}^{\star}(G+e)\leq\gamma_{rk}^{\star}(G)+1$
for $e\in E(\overline{G})$,

  2. (ii)

$\gamma_{rk}^{\star}(G)-1\leq\gamma_{rk}^{\star}(G-e)\leq\gamma_{rk}^{\star}(G)+k$
for $e\in E(G)$.

###### Proof.

(i) First, we show that
$\gamma_{rk}^{\star}(G+e)\leq\gamma_{rk}^{\star}(G)+1$. Let $f$ be
$\gamma_{rk}^{\star}(G)$-function. Clearly, we can extend $f$ to a MkRDF of
$G+e$ by assigning $\\{1\\}$ to $f(e)$.

Next, we claim that $\gamma_{rk}^{\star}(G)-k\leq\gamma_{rk}^{\star}(G+e)$.
Let $f$ be $\gamma_{rk}^{\star}(G+e)$-function and let $e=uv$. If
$f(e)=\emptyset$, then clearly the function $f|_{V(G)\cup E(G)}$ is a MkRDF of
$G$. This implies
$\gamma_{rk}^{\star}(G)-k<\gamma_{rk}^{\star}(G)\leq\gamma_{rk}^{\star}(G+e)$.

Now assume that $f(e)\neq\emptyset$. Then define $g:V(G)\cup
E(G)\rightarrow\mathcal{P}([k])$ by $g(u)=f(u)\cup f(e)$, $g(v)=f(v)\cup f(e)$
and $g(x)=f(x)$ otherwise. Clearly, $g$ ia a MkRDF of $G$ with weight
$\gamma_{rk}^{\star}(G+e)+|f(e)|$. Thus,
$\gamma_{rk}^{\star}(G)-k\leq\gamma_{rk}^{\star}(G)-|f(e)|\leq\gamma_{rk}^{\star}(G+e)$.

(ii) By (i),
$\gamma_{rk}^{\star}(G-e)-k\leq\gamma_{rk}^{\star}((G-e)+e)\leq\gamma_{rk}^{\star}(G-e)+1$.
This implies (ii). ∎

######  Theorem 2.5.

Let $T$ be a tree of order $n\geq 3$. Then
$\gamma_{r3}^{\star}(T)\leq\frac{3n}{2}$.

###### Proof.

We proceed by induction on the order $n$ of $T$. Obviously, the statement is
true for a path $P_{3}$.

Let $T$ be a tree of order $n\geq 4$. Suppose that every tree $T^{\prime}$ of
order $n^{\prime}(<n)$ satisfies
$\gamma_{r3}^{\star}(T^{\prime})\leq\frac{3n^{\prime}}{2}$. Let $f$ be a
$\gamma_{r3}^{\star}(T^{\prime})$-function. If $T$ is a star $K_{1,n-1}$, then
$\gamma_{r3}^{\star}(T)=n+1\leq\frac{3n}{2}$. Assume that $T$ is a double star
$DS_{p,q}$ with $p\geq q\geq 1$. Then
$p+q+3=n+1=\gamma_{r3}^{\star}(T)\leq\frac{3n}{2}$. Now we assume that $T$ is
neither a star or a double star. Then it is easy to see that $T$ has diameter
at least four. Among all of diametrical paths in $T$, we choose
$x_{0}x_{1}\dotsc x_{d}$ so that it maximizes the degree of $x_{d-1}$. Root
$T$ at $x_{0}$. We divide our consideration into three cases.

Case 1. $deg_{T}(x_{d-1})=t\geq 3$.

Now $T_{x_{d-1}}\cong K_{1,t-1}$. Let $T^{\prime}=T-T_{x_{d-1}}$. Applying the
induction hypothesis to $T^{\prime}$, we have
$\gamma_{r3}^{\star}(T^{\prime})\leq\frac{3(n-t)}{2}$. Define $g:V(T)\cup
E(T)\rightarrow\mathcal{P}([3])$ by
$g(x_{d-1})=g(x_{d-2}x_{d-1})=g(x_{d})=\emptyset$, $g(x_{d-1}x_{d})=[3]$,
$g(x_{d-1}x)=\emptyset$ and $g(x)=\\{1\\}$ for $x\in
C(x_{d-1})\setminus\\{x_{d}\\}$ and $g(x)=f(x)$ otherwise. Then clearly $g$ is
a M3RDF of $T$ and so

$\gamma_{r3}^{\star}(T)\leq\omega(g)=\gamma_{r3}^{\star}(T^{\prime})+t+1\leq\frac{3(n-t)}{2}+t+1=\frac{3n-t+2}{2}<\frac{3n}{2}.$

Case 2. $deg_{T}(x_{d-1})=2$ and $deg_{T}(x_{d-2})=t\geq 3$.

Now $T_{x_{d-2}}\cong S_{t-1,r}$, where $1\leq r\leq t-1$. Let
$T^{\prime}=T-T_{x_{d-2}}$. Applying the induction hypothesis to $T^{\prime}$,
we have $\gamma_{r3}^{\star}(T^{\prime})\leq\frac{3(n-t-r)}{2}$. Define
$g:V(T)\cup E(T)\rightarrow\mathcal{P}([3])$ by
$g(x_{d-3}x_{d-2})=g(x_{d-2})=g(x_{d-1})=g(x_{d-1}x_{d})=\emptyset$,
$g(x_{d-2}x_{d-1})=[3]$, $g(x_{d-2}x)=\emptyset$ for $x\in
C(x_{d-2})\setminus\\{x_{d-1}\\}$, $g(x)=\\{1\\}$ if $x\in
C(x_{d-2})\setminus\\{x_{d-1}\\}$ is a leaf, $g(x)=\emptyset$, $g(xy)=[3]$ and
$g(y)=\emptyset$ if $x\in C(x_{d-2})\setminus\\{x_{d-1}\\}$ is a support
vertex, where $y\in C(x)$, and $g(x)=f(x)$ otherwise. Then clearly $g$ is a
M3RDF of $T$ and so

$\gamma_{r3}^{\star}(T)\leq\omega(g)=\gamma_{r3}^{\star}(T^{\prime})+t+2r\leq\frac{3(n-t-r)}{2}+t+2r=\frac{3n-t+r}{2}<\frac{3n}{2}.$

Case 3. $deg_{T}(x_{d-1})=2$ and $deg_{T}(x_{d-2})=2$.

Now $T_{x_{d-2}}\cong P_{3}$. Let $T^{\prime}=T-T_{x_{d-2}}$. Applying the
induction hypothesis to $T^{\prime}$, we have
$\gamma_{r3}^{\star}(T^{\prime})\leq\frac{3(n-3)}{2}$. Define $g:V(T)\cup
E(T)\rightarrow\mathcal{P}([3])$ by
$g(x_{d-3}x_{d-2})=g(x_{d-2})=g(x_{d-1})=g(x_{d-1}x_{d})=\emptyset$,
$g(x_{d-2}x_{d-1})=[3]$, $g(x_{d})=\\{1\\}$ and $g(x)=f(x)$ otherwise. Then
clearly $g$ is a M3RDF of $T$ and so

$\gamma_{r3}^{\star}(T)\leq\omega(g)=\gamma_{r3}^{\star}(T^{\prime})+4\leq\frac{3(n-3)}{2}+4=\frac{3n-1}{2}<\frac{3n}{2}.$

∎

##  3\. The middle $3$-rainbow domination number of paths, cycles and complete
graphs

In this section, we determine the middle $3$-rainbow domination number of
paths, cycles and complete graphs.

######  Proposition 3.1.

For $n\geq 2$,

$\gamma_{r3}^{\star}(P_{n})=\left\\{\begin{array}[]{ll}\frac{4n-1}{3}&\hbox{for
$n\equiv 1$ (mod $3$);}\\\ \frac{4n+1}{3}&\hbox{for $n\equiv 2$ (mod $3$);}\\\
\frac{4n}{3}&\hbox{for $n\equiv 0$ (mod $3$).}\end{array}\right.$

###### Proof.

One can check that $\gamma_{r3}^{\star}(P_{2})=3$,
$\gamma_{r3}^{\star}(P_{3})=4$, $\gamma_{r3}^{\star}(P_{4})=5$,
$\gamma_{r3}^{\star}(P_{5})=7$ and $\gamma_{r3}^{\star}(P_{6})=8$. We proceed
by induction on $n$. Assume that $P_{n}=v_{1}v_{2}\dotsc v_{n}$ and let
$x_{2i-1}=v_{i}$ for $1\leq i\leq n$ and $x_{2i}=v_{i}v_{i+1}$ for $1\leq
i\leq n-1$. Let $V(P_{n})\cup E(P_{n})=\\{x_{1},\dotsc,x_{2n-1}\\}$ and $f$ be
a $\gamma_{r3}^{\star}(P_{n})$-function. We divide our consideration into
three cases.

Case 1. $n\equiv 1$ (mod $3$).

First, we claim that $\gamma_{r3}^{\star}(P_{n})\geq\frac{4n-1}{3}$. Assume
that $n\geq 7$. It is easy to see that $\sum_{i=1}^{5}|f(x_{i})|\geq 3$. If
$\sum_{i=1}^{5}|f(x_{i})|=3$, then $|f(x_{4})|+|f(x_{5})|=0$. To dominate
$x_{5}$, it must be $f(x_{6})=\\{1,2,3\\}$. Thus, it is easy to see that
$\sum_{i=1}^{7}|f(x_{i})|\geq 6$. Define
$h:V(P_{n}-\\{v_{1},\dotsc,v_{4}\\})\cup
E(P_{n}-\\{v_{1},\dotsc,v_{4}\\})\rightarrow\mathcal{P}([3])$ by
$h(x_{9})=f(x_{8})\cup f(x_{9})$ and $h(x_{i})=f(x_{i})$ for $10\leq i\leq
2n-1$. Clearly, $h$ is a M3KDF of $P_{n-4}$ with weight at most $\omega(f)-6$.
By the induction hypothesis, we have

$\gamma_{r3}^{\star}(P_{n})\geq\omega(h)+6\geq\gamma_{r3}^{\star}(P_{n-4})+6=\frac{4(n-4)}{3}+6=\frac{4n+2}{3}.$

Now assume that $\sum_{i=1}^{5}|f(x_{i})|\geq 4$. Define
$g:V(P_{n}-\\{v_{1},v_{2},v_{3}\\})\cup
E(P_{n}-\\{v_{1},v_{2},v_{3}\\})\rightarrow\mathcal{P}([3])$ by
$g(x_{7})=f(x_{6})\cup f(x_{7})$ and $g(x_{i})=f(x_{i})$ for $8\leq i\leq
2n-1$. Clearly, $g$ is a M3KDF of $P_{n-3}$ with weight at most $\omega(f)-4$.
By the induction hypothesis, we have

$\gamma_{r3}^{\star}(P_{n})\geq\omega(g)+4\geq\gamma_{r3}^{\star}(P_{n-3})+4=\frac{4(n-3)-1}{3}+4=\frac{4n-1}{3}.$

Next, we claim that $\gamma_{r3}^{\star}(P_{n})\leq\frac{4n-1}{3}$. Define
$h:V(P_{n})\cup E(P_{n})\rightarrow\mathcal{P}([3])$ by $h(v_{1+3i})=\\{1\\}$
for $0\leq i\leq\frac{n-1}{3}$, $h(x_{4+6i})=[3]$ for $0\leq
i\leq\frac{n-4}{3}$ and $h(x)=\emptyset$ otherwise. It is easy to see that $h$
is a M3RDF of $P_{n}$ with weight $\frac{4n-1}{3}$. Thus, we have
$\gamma_{r3}^{\star}(P_{n})=\frac{4n-1}{3}$.

Case 2. $n\equiv 2$ (mod $3$).

By the same argument as in Case 1, we can show that
$\gamma_{r3}^{\star}(P_{n})\geq\frac{4n+1}{3}$. Define $g:V(P_{n})\cup
E(P_{n})\rightarrow\mathcal{P}([3])$ by $g(v_{1+3i})=\\{1\\}$ for $0\leq
i\leq\frac{n-2}{3}$, $g(x_{4+6i})=[3]$ for $0\leq i\leq\frac{n-5}{3}$,
$g(v_{n})=\\{2,3\\}$ and $g(x)=\emptyset$ otherwise. It is easy to see that
$g$ is a M3RDF of $P_{n}$ with weight $\frac{4n+1}{3}$. Thus, we have
$\gamma_{r3}^{\star}(P_{n})=\frac{4n+1}{3}$.

Case 3. $n\equiv 0$ (mod $3$).

By the same argument as in Case 1, we can show that
$\gamma_{r3}^{\star}(P_{n})\geq\frac{4n}{3}$. Define $h:V(P_{n})\cup
E(P_{n})\rightarrow\mathcal{P}([3])$ by $h(v_{1+3i})=\\{1\\}$ for $0\leq
i\leq\frac{n-3}{3}$, $h(x_{4+6i})=[3]$ for $0\leq i\leq\frac{n-3}{3}$ and
$h(x)=\emptyset$ otherwise. It is easy to see that $h$ is a M3RDF of $P_{n}$
with weight $\frac{4n}{3}$. Thus, we have
$\gamma_{r3}^{\star}(P_{n})=\frac{4n}{3}$. ∎

######  Proposition 3.2.

For $n\geq 3$,

$\gamma_{r3}^{\star}(C_{n})=\left\\{\begin{array}[]{ll}\frac{4n+2}{3}&\hbox{for
$n\equiv 1$ (mod $3$);}\\\ \frac{4n+1}{3}&\hbox{for $n\equiv 2$ (mod $3$);}\\\
\frac{4n}{3}&\hbox{for $n\equiv 0$ (mod $3$).}\end{array}\right.$

###### Proof.

Assume that $C_{n}=v_{1}v_{2}\dotsc v_{n}v_{1}$, where the subscript $k$ of
$v_{k}$ is read by modulo $n$. Let $f$ be a
$\gamma_{r3}^{\star}(P_{n})$-function such that the size of $N:=\\{v_{i}\mid
f(v_{i})\neq\emptyset\\}$ is as small as possible. We divide our consideration
into three cases.

Case 1. $n\equiv 1$ (mod $3$).

If there exists some $k$ such that
$|f(v_{k})|+|f(v_{k}v_{k+1})|+|f(v_{k+1})|\geq 3$, then define
$g:V(P_{n}-\\{v_{k},v_{k+1}\\})\cup
E(P_{n}-\\{v_{k},v_{k+1}\\})\rightarrow\mathcal{P}([3])$ by
$g(v_{k-1})=f(v_{k-1})\cup f(v_{k-1}v_{k})$, $g(v_{k+2})=f(v_{k+1}v_{k+2})\cup
f(v_{k+2})$ and $g(x)=f(x)$ otherwise. It is easy to see that $g$ is a M3RDF
of $P_{n-2}$ with weight at most $\gamma_{r3}^{\star}(C_{n})-3$. By
Proposition 3.1, we have

$\gamma_{r3}^{\star}(C_{n})\geq\omega(g)+3\geq\gamma_{r3}^{\star}(P_{n-2})+3=\frac{4(n-2)+1}{3}+3=\frac{4n+2}{3}.$

Assume that

(1) $|f(v_{k})|+|f(v_{k}v_{k+1})|+|f(v_{k+1})|\leq 2$

for each $k\in[n]$.

If there exists some $k\in[n]$ such that $|f(v_{k})|\geq 2$, then define
$g:V(P_{n}-v_{k})\cup E(P_{n}-v_{k})\rightarrow\mathcal{P}([3])$ by
$g(v_{k-1})=f(v_{k-1})\cup f(v_{k-1}v_{k})$, $g(v_{k+1})=f(v_{k+1})\cup
f(v_{k}v_{k+1})$ and $g(x)=f(x)$ otherwise. Clearly, $g$ is a M3RDF of
$P_{n-1}$ with weight at most $\gamma_{r3}^{\star}(C_{n})-2$. By Proposition
3.1, we have

$\gamma_{r3}^{\star}(C_{n})\geq\omega(g)+2\geq\gamma_{r3}^{\star}(P_{n-1})+2\geq\frac{4(n-1)}{3}+2=\frac{4n+2}{3}.$

Assume that $|f(v_{k})|\leq 1$ for each $k\in[n]$. If $|f(v_{k})|=0$ for each
$k\in[n]$, then to dominate $v_{k}$, we must have $f(v_{k-1}v_{k})\cup
f(v_{k}v_{k+1})=[3]$. Thus, it follows from $n\geq 4$ that

$\gamma_{r3}^{\star}(C_{n})=\frac{1}{2}\sum_{1\leq k\leq n}\sum_{x\in
N_{M}(v_{k})}|f(x)|=\frac{3n}{2}\geq\frac{4n+2}{3}.$

Now assume that $N$ is not empty. For a fixed $v_{i}\in N$, if
$|f(v_{i})|+|f(v_{i}v_{i+1})|+|f(v_{i+1})|=1$, then $v_{i+1}v_{i+2}$ must
dominate $v_{i+1}$ so that $f(v_{i+1}v_{i+2})=[3]$, a contradiction to (1).
Thus, $|f(v_{i})|+|f(v_{i}v_{i+1})|+|f(v_{i+1})|=2$. By the same argument, we
have $|f(v_{i})|+|f(v_{i-1}v_{i})|+|f(v_{i-1})|=2$. Suppose that
$f(v_{i-1})\neq\emptyset$ and $f(v_{i+1})\neq\emptyset$. Without loss of
generality, assume that $f(v_{i})=\\{1\\}$, $f(v_{l-1})=\\{3\\}$ and
$f(v_{l+1})=\\{2\\}$. Then to dominate $v_{i-1}v_{i}$ and $v_{i}v_{i+1}$, we
must have $f(v_{l-2}v_{l-1})=\\{2\\}$ and $f(v_{l+1}v_{l+2})=\\{3\\}$. It
follows from (1) that $f(v_{l-2})=f(v_{l+2})=\emptyset$. To dominate $v_{i-2}$
and $v_{i+2}$, we must have $f(v_{l-3}v_{l-2})=\\{1,3\\}$ and
$f(v_{l+2}v_{l+3})=\\{1,2\\}$. It follows from (1) that
$f(v_{l-3})=f(v_{l+3})=\emptyset$. To dominate $v_{i-3}$ and $v_{i+3}$, we
must have $\\{2\\}\subseteq f(v_{l-4}v_{l-3})$ and $\\{3\\}\subseteq
f(v_{l+3}v_{l+4})$. Define $g:V(C_{n})\cup
E(C_{n})\rightarrow\mathcal{P}([3])$ by $g(v_{i-3})=g(v_{i+3})=\\{1\\}$,
$g(v_{i-2}v_{i-1})=g(v_{i+1}v_{i+2})=[3]$,
$g(v_{i-3}v_{i-2})=g(v_{i-2})=g(v_{i-1})=g(v_{i-1}v_{i})=g(v_{i}v_{i+1})=g(v_{i+1})=g(v_{i+2})=g(v_{i+2}v_{i+3})=\emptyset$
and $g(x)=f(x)$ otherwise. Then $g$ is a M3RDF of $C_{n}$ with weight
$\omega(f)$. As above, this implies that
$\gamma_{r3}^{\star}(C_{n})\geq\frac{4n+2}{3}$.

Now assume that for each $v_{i}\in N$, $|f(v_{i-1}v_{i})|=1$ or
$|f(v_{i}v_{i+1})|=1$. Since $\sum_{x\in N_{M}[v_{i}]}|f(x)|\geq 2$ for
$v_{i}\in N$ and $\sum_{x\in N_{M}[v_{i}]}|f(x)|=3$ for $v_{i}\in
V(C_{n})\setminus N$, we have

$\gamma_{r3}^{\star}(C_{n})\geq\frac{3(n-t)}{2}+(t+\frac{t}{2})=\frac{3n}{2}\geq\frac{4n+2}{3},$

where $t=|N|$.

By Theorem 2.4, $\gamma_{r3}^{\star}(C_{n})\leq\gamma_{r3}^{\star}(P_{n})+1$.
Thus, we have $\gamma_{r3}^{\star}(C_{n})=\frac{4n+2}{3}$.

Case 2. $n\equiv 2$ (mod $3$).

If there exists some $k$ such that
$|f(v_{k})|+|f(v_{k}v_{k+1})|+|f(v_{k+1})|\geq 3$, then define
$g:V(P_{n}-\\{v_{k},v_{k+1}\\})\cup
E(P_{n}-\\{v_{k},v_{k+1}\\})\rightarrow\mathcal{P}([3])$ by
$g(v_{k-1})=f(v_{k-1})\cup f(v_{k-1}v_{k})$, $g(v_{k+2})=f(v_{k+1}v_{k+2})\cup
f(v_{k+2})$ and $g(x)=f(x)$ otherwise. It is easy to see that $g$ is a M3RDF
of $P_{n-2}$ with weight at most $\gamma_{r3}^{\star}(C_{n})-3$. By
Proposition 3.1, we have

$\gamma_{r3}^{\star}(C_{n})\geq\omega(g)+3\geq\gamma_{r3}^{\star}(P_{n-2})+3=\frac{4(n-2)}{3}+3=\frac{4n+1}{3}.$

Now suppose that

$|f(v_{k})|+|f(v_{k}v_{k+1})|+|f(v_{k+1})|\leq 2$

for each $k\in[n]$.

If there exists some $k\in[n]$ such that $|f(v_{k})|\geq 2$, then define
$g:V(P_{n}-v_{k})\cup E(P_{n}-v_{k})\rightarrow\mathcal{P}([3])$ by
$g(v_{k-1})=f(v_{k-1})\cup f(v_{k-1}v_{k})$, $g(v_{k+1})=f(v_{k+1})\cup
f(v_{k}v_{k+1})$ and $g(x)=f(x)$ otherwise. Clearly, $g$ is a M3RDF of
$P_{n-1}$ with weight at most $\gamma_{r3}^{\star}(C_{n})-2$. By Proposition
3.1, we have

$\gamma_{r3}^{\star}(C_{n})\geq\omega(g)+2\geq\gamma_{r3}^{\star}(P_{n-1})+2\geq\frac{4(n-1)-1}{3}+2=\frac{4n+1}{3}.$

Assume that $|f(v_{k})|\leq 1$ for each $k\in[n]$. By the same argument as
Case 1, we have $\gamma_{r3}^{\star}(C_{n})\geq\frac{4n+1}{3}$.

Define $h:V(C_{n})\cup E(C_{n})\rightarrow\mathcal{P}([3])$ by
$h(v_{1+3i})=\\{1\\}$ for $0\leq i\leq\frac{n-6}{3}$,
$h(v_{2+3i}v_{3+3i})=[3]$ for $0\leq i\leq\frac{n-6}{3}$,
$h(v_{n-1}v_{n})=[3]$ and $h(x)=\emptyset$ otherwise. It is easy to see that
$h$ is a M3RDF of $C_{n}$ with weight $\frac{4n+1}{3}$. Thus, we have
$\gamma_{r3}^{\star}(C_{n})=\frac{4n+1}{3}$.

Case 3. $n\equiv 0$ (mod $3$).

If there exists some $k\in[n]$ such that $|f(v_{k})|\geq 1$, then define
$g:V(P_{n}-v_{k})\cup E(P_{n}-v_{k})\rightarrow\mathcal{P}([3])$ by
$g(v_{k-1})=f(v_{k-1})\cup f(v_{k-1}v_{k})$, $g(v_{k+1})=f(v_{k+1})\cup
f(v_{k}v_{k+1})$ and $g(x)=f(x)$ otherwise. Clearly, $g$ is a M3RDF of
$P_{n-1}$ with weight at most $\gamma_{r3}^{\star}(C_{n})-1$. By Proposition
3.1, we have

$\gamma_{r3}^{\star}(C_{n})\geq\omega(g)+1\geq\gamma_{r3}^{\star}(P_{n-1})+1\geq\frac{4(n-1)+1}{3}+1=\frac{4n}{3}.$

Assume that $|f(v_{i})|=0$ for each $i\in[n]$. If there exists some $k\in[n]$
such that $|f(v_{k}v_{k+1})|=3$, then define
$g:V(P_{n}-\\{v_{k},v_{k+1}\\})\cup
E(P_{n}-\\{v_{k},v_{k+1}\\})\rightarrow\mathcal{P}([3])$ by
$g(v_{k-1})=f(v_{k-1})\cup f(v_{k-1}v_{k})$, $g(v_{k+2})=f(v_{k+2})\cup
f(v_{k+1}v_{k+2})$ and $g(x)=f(x)$ otherwise. Clearly, $g$ is a M3RDF of
$P_{n-2}$ with weight at most $\gamma_{r3}^{\star}(C_{n})-3$. By Proposition
3.1, we have

$\gamma_{r3}^{\star}(C_{n})\geq\omega(g)+3\geq\gamma_{r3}^{\star}(P_{n-2})+3\geq\frac{4(n-2)-1}{3}+3=\frac{4n}{3}.$

Now assume that $|f(v_{i}v_{i+1})|\leq 2$ for each $i\in[n]$. Then the
assignment of edges under $f$ should start one of the following : (i)
$\\{1\\},\\{2,3\\},\\{1\\},\\{2,3\\}\dotsc$, (ii)
$\\{2\\},\\{1,3\\},\\{2\\},\\{1,3\\}\dotsc$, (iii)
$\\{3\\},\\{1,2\\},\\{3\\},\\{1,2\\}\dotsc$. Thus, one can check that

$\gamma_{r3}^{\star}(C_{n})\geq\lceil\frac{n}{2}\rceil+2\lfloor\frac{n}{2}\rfloor\geq\frac{4n}{3}.$

Therefore, we have $\gamma_{r3}^{\star}(C_{n})\geq\frac{4n}{3}$.

Define $h:V(C_{n})\cup E(C_{n})\rightarrow\mathcal{P}([3])$ by
$h(v_{1+3i})=\\{1\\}$ for $0\leq i\leq\frac{n-3}{3}$,
$h(v_{2+3i}v_{3+3i})=[3]$ for $0\leq i\leq\frac{n-3}{3}$ and $h(x)=\emptyset$
otherwise. It is easy to see that $h$ is a M3RDF of $C_{n}$ with weight
$\frac{4n}{3}$. Thus, we have $\gamma_{r3}^{\star}(C_{n})=\frac{4n}{3}$.

∎

######  Proposition 3.3.

For $n\geq 2$,

$\gamma_{r3}^{\star}(K_{n})=\left\\{\begin{array}[]{ll}\frac{3n}{2}&\hbox{if
$n$ is even;}\\\ \frac{3n-1}{2}&\hbox{if $n$ is odd.}\end{array}\right.$

###### Proof.

Let $V(K_{n})=\\{v_{1},\dotsc,v_{n}\\}$. If $n$ is odd, then define
$g:V(K_{n})\cup E(K_{n})\rightarrow\mathcal{P}([3])$ by $g(v_{1})=\\{1\\}$,
$g(v_{2i}v_{2i+1})=[3]$ for $1\leq i\leq\frac{n-1}{2}$ and $g(x)=\emptyset$
otherwise. It is easy to see that $g$ is a M3RDF of $K_{n}$ with weight
$\frac{3n-1}{2}$. If $n$ is even, then define $h:V(K_{n})\cup
E(K_{n})\rightarrow\mathcal{P}([3])$ by $h(v_{2i-1}v_{2i})=[3]$ for $1\leq
i\leq\frac{n}{2}$ and $h(x)=\emptyset$ otherwise. It is easy to see that $h$
is a M3RDF of $K_{n}$ with weight $\frac{3n}{2}$.

Now we claim that $\gamma_{r3}^{\star}(K_{n})\geq\frac{3n}{2}$ if $n$ is even
and $\gamma_{r3}^{\star}(K_{n})\geq\frac{3n-1}{2}$ if $n$ is odd. One can
easily check that $\gamma_{r3}^{\star}(K_{2})=3$,
$\gamma_{r3}^{\star}(K_{3})=4$, and $\gamma_{r3}^{\star}(K_{4})=6$. We proceed
by induction on $n$. Assume that $n\geq 5$.

Case 1. $n$ is odd.

Let $f$ be a $\gamma_{r3}^{\star}(K_{n})$-function. If
$\sum_{i=1}^{n}|f(v_{i})|=0$, then to dominate each $v_{i}$ we must have
$[3]\subseteq\cup_{e\in N_{M}(v_{i})}f(e)$ for each $v_{i}\in V(K_{n})$. This
implies that

$2\gamma_{r3}^{\star}(K_{n})=\sum_{i=1}^{n}\sum_{e\in N_{M}(v_{i})}|f(e)|\geq
3n.$

Thus, $\gamma_{r3}^{\star}(K_{n})>\frac{3n-1}{2}$.

Assume that $\sum_{i=1}^{n}|f(v_{i})|\neq 0$. Without loss of generality,
assume that $f(v_{1})\neq\emptyset$. Define $g:V(K_{n}-v_{1})\cup
E(K_{n}-v_{1})\rightarrow\mathcal{P}([3])$ by $g(v_{i})=f(v_{i})\cup
f(v_{1}v_{i})$ for $2\leq i\leq n$ and $g(x)=f(x)$ otherwise. Then $g$ is a
M3RDF with weight at most $\gamma_{r3}^{\star}(K_{n})-1$. By the induction
hypothesis, we have

$\gamma_{r3}^{\star}(K_{n})\geq\omega(g)+1\geq\gamma_{r3}^{\star}(K_{n-1})+1=\frac{3(n-1)}{2}+1=\frac{3n-1}{2}.$

Case 2. $n$ is even.

We choose a $\gamma_{r3}^{\star}(K_{n})$-function $f$ so that the size of
$\\{v_{i}\in V(K_{n})\mid f(v_{i})\neq\emptyset\\}$ is as small as possible.

For an edge $v_{i}v_{j}\in E(K_{n})$, if
$|f(v_{i})|+|f(v_{j})|+|f(v_{i}v_{j})|=3$, then define
$h:V(K_{n}-\\{v_{i},v_{j}\\})\cup
E(K_{n}-\\{v_{i},v_{j}\\})\rightarrow\mathcal{P}([3])$ by
$h(v_{k})=f(v_{k})\cup f(v_{k}v_{i})\cup f(v_{k}v_{j})$ for $v_{k}\in
V(K_{n})\setminus\\{v_{i},v_{j}\\}$ and $h(x)=f(x)$ otherwise. Clearly $h$ is
a M3RDF with weight $\gamma_{r3}^{\star}(K_{n})-3$. By the induction
hypothesis, we have

$\gamma_{r3}^{\star}(K_{n})\geq\omega(h)+3\geq\gamma_{r3}^{\star}(K_{n-2})+3=\frac{3(n-2)}{2}+3=\frac{3n}{2}.$

Assume that $|f(v_{i})|+|f(v_{j})|+|f(v_{i}v_{j})|\leq 2$ for any
$v_{i},v_{j}\in V(K_{n})$.

For a vertex $v_{i}\in V(K_{n})$, if $|f(v_{i})|=2$, then define
$g:V(K_{n}-v_{i})\cup E(K_{n}-v_{i})\rightarrow\mathcal{P}([3])$ by
$g(v_{k})=f(v_{k})\cup f(v_{k}v_{i})$ for $v_{k}\in
V(K_{n})\setminus\\{v_{i}\\}$ and $g(x)=f(x)$ otherwise. Clearly $g$ is a
M3RDF with weight $\gamma_{r3}^{\star}(K_{n})-2$. By the induction hypothesis,
we have

$\gamma_{r3}^{\star}(K_{n})\geq\omega(g)+2\geq\gamma_{r3}^{\star}(K_{n-1})+2=\frac{3(n-1)-1}{2}+2=\frac{3n}{2}.$

Assume that $|f(v_{i})|\leq 1$ for each $v_{i}\in V(K_{n})$.

Let $N:=\\{v_{i}\in V(K_{n})\mid f(v_{i})\neq\emptyset\\}$. For a fixed
$v_{i}\in N$, suppose that there exists no $v_{j}\in V(K_{n})$ such that
$f(v_{i}v_{j})\neq\emptyset$. Without loss of generality, we may assume that
$f(v_{i})=\\{1\\}$. To dominate elements in $\\{v_{i}v_{k}\mid v_{k}\in
V(K_{n})\setminus\\{v_{i}\\}\\}$, $\bigcup_{x\in N_{M}[v_{k}]}f(x)$ should
contain $2$ and $3$ for each $v_{k}\in V(K_{n})\setminus\\{v_{i}\\}$. Thus, we
have $s_{2},s_{3}\geq\frac{n}{2}$, where $s_{j}:=|\\{x\in V(K_{n}-v_{i})\cup
E(K_{n}-v_{i})\mid j\in f(x)\\}|$. If $f(x)\neq\emptyset$ for all $x\in
N_{M}[v_{k}]\setminus\\{v_{i}v_{k}\\}$, then $\sum_{x\in
N_{M}[v_{k}]}|f(x)|\geq n$. This implies
$\gamma_{r3}^{\star}(K_{n})\geq\frac{3n}{2}$. Assume that for $v_{k}\in
V(K_{n})\setminus\\{v_{i}\\}$ there exists $x\in
N_{M}[v_{k}]\setminus\\{v_{i}v_{k}\\}$ such that $f(x)=\emptyset$. Then to
dominate such an element $x$, $\bigcup_{y\in N_{M}(x)}f(y)$ should contain
$1$. Thus, we have $s_{1}\geq\frac{n}{2}$ so that
$\omega(f)\geq|f(v_{i})|+s_{2}+s_{3}+s_{1}=1+\frac{3n}{2}$.

Assume that for each $v_{i}\in N$ there exists a vertex $v_{j}\in V(K_{n})$
such that $f(v_{i}v_{j})\neq\emptyset$. Let $t$ be the size of set $N$. For
$v_{j}\in V(K_{n})\setminus N$, $\bigcup_{x\in N_{M}[v_{j}]}f(x)$ should
contain $[3]$. For $v_{i}\in N$, $\bigcup_{x\in N_{M}(v_{i})}f(x)$ contains at
least one element. Thus, we have
$\gamma_{r3}^{\star}(K_{n})\geq\frac{3(n-t)}{2}+(t+\frac{t}{2})=\frac{3n}{2}$.
This completes the proof. ∎

##  4\. Lower and upper bounds for trees

In this section, we provide lower and upper bounds for the middle $3$-rainbow
domination number of trees in terms of the matching number.

######  Theorem 4.1.

For every tree $T$ of order $n$, $\gamma_{r3}^{\star}(T)\leq
n+\alpha^{\prime}(T)$.

###### Proof.

Take a maximum matching $M$ in $T$. Let $U$ be the set of vertices which are
not saturated by $M$. Define a function by $f(e)=[3]$ for $e\in M$,
$f(u)=\\{1\\}$ for $u\in U$ and $f(x)=\emptyset$ otherwise. Clearly, $f$ is a
M3RDF of $T$. Thus,
$\gamma_{r3}^{\star}(T)\leq|U|+3|M|=(n-2\alpha^{\prime}(T))+3\alpha^{\prime}(T)=n+\alpha^{\prime}(T)$.
∎

######  Lemma 4.2.

Let $T$ be a tree and $P_{3}=uvw$ a path in $T$ with $deg_{T}(v)=2$ and
$deg_{T}(w)=1$. Then $|f(uv)|+|f(v)|+|f(vw)|+|f(w)|\geq 3$ for any
$\gamma_{r3}^{\star}(T)$-function $f$.

###### Proof.

If $f(w)=\emptyset$, then to dominate $w$ it follows that $f(vw)=[3]$. If
$f(vw)=\emptyset$, then to dominate $vw$ it follows that $f(uv)\cup f(v)\cup
f(w)=[3]$. If $f(v)=\emptyset$, then to dominate $v$ it follows that
$f(uv)\cup f(vw)=[3]$. In the above cases, we have
$|f(uv)|+|f(v)|+|f(vw)|+|f(w)|\geq 3$. If $f(w)$, $f(vw)$ and $f(v)$ are not
empty, then $|f(uv)|+|f(v)|+|f(vw)|+|f(w)|\geq 3$. This completes the proof. ∎

######  Theorem 4.3.

For every tree $T$, $\gamma_{r3}^{\star}(T)\geq\frac{5\alpha^{\prime}(T)}{2}$.

###### Proof.

We proceed by induction on the order $n$ of $T$. Obviously, the statement is
true for all trees of order $n\leq 4$.

Let $T$ be a tree of order $n\geq 5$. Suppose that every tree $T^{\prime}$ of
order $n^{\prime}(<n)$ satisfies
$\gamma_{r3}^{\star}(T^{\prime})\geq\frac{5\alpha^{\prime}(T^{\prime})}{2}$.
Let $M$ be a maximum matching in $T$. If $T$ is a star, then
$\alpha^{\prime}(T)=1$ and so $n+1=\gamma_{r3}^{\star}(T)>\frac{5}{2}$. Assume
that $T$ is a double star $DS_{p,q}$ with $p\geq q\geq 1$. Then
$\alpha^{\prime}(T)=2$ and so $n+1=\gamma_{r3}^{\star}(T)>5$. Now we assume
that $T$ is neither a star or a double star. Then it is easy to see that $T$
has diameter at least four.

If $T$ has a pendant edge $uv$ such that $v$ is a leaf and $uv\not\in M$, then
for any $\gamma_{r3}^{\star}(T)$-function $f$, the function $g:V(T-v)\cup
E(T-v)$ defined by by $g(u)=f(u)\cup f(uv)$ and $g(x)=f(x)$ otherwise is a
M3RDF of $T-v$ with weight at most $\omega(f)$. By the induction hypothesis,
we have
$\gamma_{r3}^{\star}(T)\geq\gamma_{r3}^{\star}(T-v)\geq\frac{5\alpha^{\prime}(T-v)}{2}=\frac{5\alpha^{\prime}(T)}{2}$.
Thus, we assume the following.

Assumption 1. All pendant edges of $T$ belong to each maximum matching.

Then it follows that all support vertices have degree $2$. If $\Delta(T)=2$,
then $T$ is a path. So, the result follows by Proposition 3.1. From now on,
assume that $\Delta(T)\geq 3$. Among all of diametrical paths in $T$, we
choose $x_{0}x_{1}\dotsc x_{d}$ so that it maximizes the size of $f(x_{d-2})$.
Root $T$ at $x_{0}$. It follows from Lemma 4.2 that
$|f(x_{d-2}x_{d-1})|+|f(x_{d-1})|+|f(x_{d-1}x_{d})|+|f(x_{d})|\geq 3$. We
divide our consideration into three cases.

Case 1. $deg(x_{d-2})\geq 3$.

First, suppose that there is a path $x_{d-2}yz$ in $T$ such that $z$ is a leaf
and $y\not\in\\{x_{d-3},x_{d-1}\\}$. Then it follows from Lemma 4.2 that
$|f(z)|+|f(yz)|+|f(y)|+|f(x_{d-2}y)|\geq 3$. Without loss of generality, we
may assume that

(2) $|f(x_{d-2}y)|\geq|f(x_{d-2}x_{d-1})|.$

Let $T^{\prime}=T-\\{x_{d-1},x_{d}\\}$. Then clearly
$\alpha^{\prime}(T^{\prime})=\alpha^{\prime}(T)-1$. Since both $f(x_{d-2}y)$
and $f(x_{d-2}x_{d-1})$ are not $[3]$, the assumption (2) implies that
$f|_{V(T^{\prime})\cup E(T^{\prime})}$ is a M3RDF of $T^{\prime}$ with weight
at most $\omega(f)-3$. By the induction hypothesis, we have
$\gamma_{r3}^{\star}(T)\geq\gamma_{r3}^{\star}(T^{\prime})+3\geq\frac{5\alpha^{\prime}(T^{\prime})}{2}+3=\frac{5(\alpha^{\prime}(T)-1)}{2}+3>\frac{5\alpha^{\prime}(T)}{2}$.

Now assume that every element of $C(x_{d-2})\setminus\\{x_{d-1}\\}$ is a leaf.
Then it follows from Assumption 1 that $|C(x_{d-2})\setminus\\{x_{d-1}\\}|=1$.
Let $v\in C(x_{d-2})\setminus\\{x_{d-1}\\}$. If $f(v)=\emptyset$, then
$x_{d-2}v$ can not dominate $v$. Thus, we must have $f(v)\neq\emptyset$. We
consider the following subcases.

Subcase 1.1. $|f(x_{d-2}x_{d-1})|\leq 1$.

This implies that $|f(x_{d-1})|+|f(x_{d-1}x_{d})|+|f(x_{d})|=3$. Let
$T^{\prime}=T-\\{x_{d-1},x_{d}\\}$. Define $g:V(T^{\prime})\cup
E(T^{\prime})\rightarrow\mathcal{P}([3])$ by $g(x_{d-2})=f(x_{d-2})\cup
f(x_{d-2}x_{d-1})$ and $g(x)=f(x)$ otherwise. Clearly $g$ is a M3RDF of
$T^{\prime}$ with weight $\omega(f)-3$. The result follows as above.

Subcase 1.2. $|f(x_{d-2}x_{d-1})|\geq 2$.

It is easy to see that
$|f(x_{d-1})|+|f(x_{d-1}x_{d})|+|f(x_{d})|=4-|f(x_{d-2}x_{d-1})|$. Let
$T^{\prime}=T-\\{x_{d-2},v,x_{d-1},x_{d}\\}$. Define $g:V(T^{\prime})\cup
E(T^{\prime})\rightarrow\mathcal{P}([3])$ by $g(x_{d-3})=f(x_{d-3})\cup
f(x_{d-3}x_{d-2})$ and $g(x)=f(x)$ otherwise. Clearly $g$ is a M3RDF of
$T^{\prime}$ with weight $\omega(f)-5$. By the induction hypothesis, we have
$\gamma_{r3}^{\star}(T)\geq\gamma_{r3}^{\star}(T^{\prime})+5\geq\frac{5\alpha^{\prime}(T^{\prime})}{2}+5=\frac{5(\alpha^{\prime}(T)-2)}{2}+5=\frac{5\alpha^{\prime}(T)}{2}$.

Case 2. $deg(x_{d-2})=2$ and $deg(x_{d-3})\geq 3$.

It follows from Assumption 1 that $x_{d-3}x_{d-2},x_{d-1}x_{d}\in M$. If there
exists a path $x_{d-3}xyz$ in $T$ such that $x\not\in\\{x_{d-2},x_{d-4}\\}$
and $z$ is a leaf. By Case 1 and Assumption 1, we may assume that
$deg(x)=deg(y)=2$. It follows from Assumption 1 and $x_{d-3}x_{d-2}\in M$ that
$x_{d-3}x,xy\not\in M$. But, $(M\setminus\\{yz\\})\cup\\{xy\\}$ is a maximum
matching in $T$ not containing a pendant edge, a contradiction.

It follows from $deg(x_{d-3})\geq 3$ that there exists a path $x_{d-3}yz$ such
that $deg(y)=2$ and $z$ is a leaf. By Lemma 4.2, we have
$|f(x_{d-2}x_{d-1})|+|f(x_{d-1})|+|f(x_{d-1}x_{d})|+|f(x_{d})|\geq 3$ and
$|f(x_{d-3}y)|+|f(y)|+|f(yz)|+|f(z)|\geq 3$.

Since $f$ is a $\gamma_{r3}^{\star}(T)$-function, it is easy to see that

$4\geq S(x_{d-3}yz)\geq 3~{}\text{and}~{}6\geq
S(x_{d-3}x_{d-2}x_{d-1}x_{d})\geq 4,$

where $S(x_{d-3}yz):=|f(x_{d-3})|+|f(x_{d-3}y)|+|f(y)|+|f(yz)|+|f(z)|$ and
$S(x_{d-3}x_{d-2}x_{d-1}x_{d}):=|f(x_{d-3})|+|f(x_{d-3}x_{d-2})|+|f(x_{d-2})|+|f(x_{d-2}x_{d-1})|+|f(x_{d-1})|+|f(x_{d-1}x_{d})|+|f(x_{d})|$.

If $S(x_{d-3}x_{d-2}x_{d-1}x_{d})=6$, then without loss of generality we may
assume that $f(x_{d-3}x_{d-2})=f(x_{d-1}x_{d})=[3]$. Let
$T^{\prime}=T-\\{x_{d-1},x_{d}\\}$. The function $f|_{V(T^{\prime})\cup
E(T^{\prime})}$ is a M3RDF of $T^{\prime}$ with weight $\omega(f)-3$. By the
induction hypothesis, we have
$\gamma_{r3}^{\star}(T)\geq\gamma_{r3}^{\star}(T^{\prime})+3\geq\frac{5\alpha^{\prime}(T^{\prime})}{2}+3=\frac{5(\alpha^{\prime}(T)-1)}{2}+3>\frac{5\alpha^{\prime}(T)}{2}$.

If $S(x_{d-3}yz)=3$, then $|f(y)|+|f(yz)|+|f(z)|=3$ and
$f(x_{d-3})=f(x_{d-3}y)=\emptyset$. Let $T^{\prime}=T-\\{y,z\\}$. The function
$f|_{V(T^{\prime})\cup E(T^{\prime})}$ is a M3RDF of $T^{\prime}$ with weight
$\omega(f)-3$. The result follows as above.

Now we assume that $S(x_{d-3}yz)=4$ and $5\geq
S(x_{d-3}x_{d-2}x_{d-1}x_{d})\geq 4$. Then without loss of generality we may
assume that $f(x_{d-3}y)=[3]$ and $f(z)=\\{1\\}$.

If $S(x_{d-3}x_{d-2}x_{d-1}x_{d})=5$, then define $g:V(T)\cup
E(T)\rightarrow\mathcal{P}([3])$ by $g(x_{d-2})=\\{1\\}$,
$g(x_{d-1}x_{d})=[3]$ and
$f(x_{d-3})=f(x_{d-3}x_{d-2})=f(x_{d-2}x_{d-1})=f(x_{d-1})=f(x_{d})=\emptyset$.
Clearly $g$ is a M3RDF of $T$ with weight $\omega(f)-1$, a contradiction.

Assume that $S(x_{d-3}x_{d-2}x_{d-1}x_{d})=4$. Then without loss of generality
we may assume that $f(x_{d-2})=\\{1\\}$ and $f(x_{d-1}x_{d})=[3]$. Let
$T^{\prime}=T-\\{x_{d-1},x_{d}\\}$. The function $f|_{V(T^{\prime})\cup
E(T^{\prime})}$ is a M3RDF of $T^{\prime}$ with weight $\omega(f)-3$. The
result follows as above.

Case 3. $deg(x_{d-2})=2$ and $deg(x_{d-3})=2$.

If $f(x_{d-4}x_{d-3})=[3]$, then it is easy to see that
$|f(x_{d-3})|+|f(x_{d-3}x_{d-2})|+|f(x_{d-2})|+|f(x_{d-2}x_{d-1})|+|f(x_{d-1})|+|f(x_{d-1}x_{d})|+|f(x_{d})|=4$,
since $f$ is a $\gamma_{r3}^{\star}(T)$-function. Without loss of generality,
we may assume that $f(x_{d-1}x_{d})=[3]$, $f(x_{d-2})=\\{1\\}$ and
$f(x_{d-3})=f(x_{d-3}x_{d-2})=f(x_{d-2}x_{d-1})=f(x_{d-1})=f(x_{d})=\emptyset$.
Let $T^{\prime}=T-\\{x_{d-1},x_{d}\\}$. Then clearly
$\alpha^{\prime}(T^{\prime})=\alpha^{\prime}(T)-1$ and $f|_{V(T^{\prime})\cup
E(T^{\prime})}$ is a M3RDF of $T^{\prime}$ with weight at most $\omega(f)-3$.
By the induction hypothesis, we have
$\gamma_{r3}^{\star}(T)\geq\gamma_{r3}^{\star}(T^{\prime})+3\geq\frac{5\alpha^{\prime}(T^{\prime})}{2}+3=\frac{5(\alpha^{\prime}(T)-1)}{2}+3>\frac{5\alpha^{\prime}(T)}{2}$.

If $f(x_{d-4}x_{d-3})\neq[3]$, then it is easy to see that
$|f(x_{d-3})|+|f(x_{d-3}x_{d-2})|+|f(x_{d-2})|+|f(x_{d-2}x_{d-1})|+|f(x_{d-1})|+|f(x_{d-1}x_{d})|+|f(x_{d})|=5$,
since $f$ is a $\gamma_{r3}^{\star}(T)$-function. Without loss of generality,
we may assume that $f(x_{d-3})=f(x_{d})=\\{1\\}$, $f(x_{d-2}x_{d-1})=[3]$ and
$f(x_{d-3}x_{d-2})=f(x_{d-2})=f(x_{d-1})=f(x_{d-1}x_{d})=\emptyset$.

Let $T^{\prime}=T-T_{x_{d-3}}$. Define $g:V(T^{\prime})\cup
E(T^{\prime})\rightarrow\mathcal{P}([3])$ by $g(x_{d-4})=f(x_{d-4})\cup
f(x_{d-4}x_{d-3})$ and $g(x)=f(x)$ otherwise. Then clearly
$\alpha^{\prime}(T^{\prime})=\alpha^{\prime}(T)-2$ and $g$ is a M3RDF of
$T^{\prime}$ with weight at most $\omega(f)-5$. By the induction hypothesis,
we have
$\gamma_{r3}^{\star}(T)\geq\gamma_{r3}^{\star}(T^{\prime})+5\geq\frac{5\alpha^{\prime}(T^{\prime})}{2}+5=\frac{5(\alpha^{\prime}(T)-2)}{2}+5=\frac{5\alpha^{\prime}(T)}{2}$.
This completes the proof. ∎

##  5\. The $3$-rainbow domatic number for the middle graph of paths and
cycles

In this section, we determine the $3$-rainbow domatic number for the middle
graph of paths and cycles.

######  Theorem 5.1 (See [11]).

If $G$ is a graph of order $n$, then $\gamma_{rk}(G)\cdot d_{rk}(G)\leq kn$.

######  Theorem 5.2 (See [11]).

For every graph $G$, $d_{rk}(G)\leq\delta(G)+k$.

######  Proposition 5.3.

For $n\geq 4$ and $n\equiv 0$ (mod $2$), $d_{r3}(M(P_{n}))=4$.

###### Proof.

By Theorem 5.2, $d_{r3}(M(P_{n}))\leq 4$.

Let $P_{n}=v_{1}v_{2}\dotsc v_{n}$. Define the $3$-rainbow dominating
functions $f_{1},f_{2},f_{3},f_{4}$ as follows:

$f_{1}(v_{1+2i}v_{2+2i})=[3]$ for $0\leq i\leq\frac{n-2}{2}$ and
$f_{1}(x)=\emptyset$ otherwise,

$f_{2}(v_{1+2i})=\\{1\\}$, $f_{2}(v_{2+2i})=\\{2\\}$ for $0\leq
i\leq\frac{n-2}{2}$, $f_{2}(v_{2+2i}v_{3+2i})=\\{3\\}$ for $0\leq
i\leq\frac{n-4}{2}$ and $f_{2}(x)=\emptyset$ otherwise,

$f_{3}(v_{1+2i})=\\{2\\}$, $f_{3}(v_{2+2i})=\\{3\\}$ for $0\leq
i\leq\frac{n-2}{2}$, $f_{3}(v_{2+2i}v_{3+2i})=\\{1\\}$ for $0\leq
i\leq\frac{n-4}{2}$ and $f_{3}(x)=\emptyset$ otherwise,

$f_{4}(v_{1+2i})=\\{3\\}$, $f_{4}(v_{2+2i})=\\{1\\}$ for $0\leq
i\leq\frac{n-2}{2}$, $f_{4}(v_{2+2i}v_{3+2i})=\\{2\\}$ for $0\leq
i\leq\frac{n-4}{2}$ and $f_{4}(x)=\emptyset$ otherwise.

Then clearly $f_{i}$ is a $3$-rainbow dominating function on $M(P_{n})$ for
each $i$. Thus, $\\{f_{1},f_{2},f_{3},f_{4}\\}$ is a family of $3$-rainbow
dominating functions on $M(P_{n})$.

∎

######  Proposition 5.4.

For $n\geq 4$, $d_{r3}(M(C_{n}))=4$.

###### Proof.

By Theorem 5.1, $\gamma_{r3}(M(C_{n}))\cdot d_{r3}(M(C_{n}))\leq 3\cdot 2n$.
It follows from Proposition 3.2 that $d_{r3}(M(C_{n}))\leq 4$.

Let $C_{n}=v_{1}v_{2}\dotsc v_{n}v_{1}$. We consider the following two cases.

Case 1. $n$ is even.

Extend the $3$-rainbow dominating functions $f_{1},f_{2},f_{3},f_{4}$ in
Proposition 5.3 as follows:

$g_{1}(v_{n}v_{1})=\emptyset$ and $g_{1}(x)=f_{1}(x)$ otherwise,

$g_{2}(v_{n}v_{1})=\\{1\\}$ and $g_{2}(x)=f_{2}(x)$ otherwise,

$g_{3}(v_{n}v_{1})=\\{1\\}$ and $g_{3}(x)=f_{3}(x)$ otherwise,

$g_{4}(v_{n}v_{1})=\\{1\\}$ and $g_{4}(x)=f_{4}(x)$ otherwise.

Case 2. $n$ is odd.

Then $n-1\geq 4$ is even. Let $f_{1},f_{2},f_{3},f_{4}$ be the $3$-rainbow
dominating functions on $M(P_{n-1})$ given by Proposition 5.3. Extend them as
follows:

$g_{1}(v_{n-1}v_{n})=\emptyset$, $g_{1}(v_{n})=\\{1\\}$,
$g_{1}(v_{n}v_{1})=\emptyset$ and $g_{1}(x)=f_{1}(x)$ otherwise,

$g_{2}(v_{n-1}v_{n})=\\{3\\}$, $g_{2}(v_{n})=\\{2\\}$,
$g_{2}(v_{n}v_{1})=\emptyset$ and $g_{2}(x)=f_{2}(x)$ otherwise,

$g_{3}(v_{n-1}v_{n})=\\{1\\}$, $g_{3}(v_{n})=\\{3\\}$,
$g_{3}(v_{n}v_{1})=\emptyset$ and $g_{3}(x)=f_{3}(x)$ otherwise,

$g_{4}(v_{n-1}v_{n})=\emptyset$, $g_{4}(v_{n})=\emptyset$,
$g_{4}(v_{n}v_{1})=[3]$ and $g_{4}(x)=f_{4}(x)$ otherwise.

In any case, clearly $g_{i}$ is a $3$-rainbow dominating function on
$M(C_{n})$ for each $i$. Thus, $\\{g_{1},g_{2},g_{3},g_{4}\\}$ is a family of
$3$-rainbow dominating functions on $M(C_{n})$. ∎

## References

  * [1] J.A. Bondy, U.S.R. Murty, Graph theory, Graduate Texts in Mathematics 244, Springer, 2007.
  * [2] B. Bre$\acute{s}$ar, Rainbow domination in graphs, in: T. W. Haynes, S. T. Hedetniemi and M. A. Henning (eds.), Topics in Domination in Graphs, Springer International Publishing, Switzerland, 2020.
  * [3] B. Bre$\acute{s}$ar, M.A. Henning, D.F. Rall, Rainbow domination in graphs, Taiwanese J. Math. 12 (2008) 213–225.
  * [4] G.J. Chang, J.J. Wu, X.D. Zhu, Rainbow domination on trees, Discrete Appl. Math. 158 (2010) 8–12.
  * [5] V.J.A. Cynthia, A. Kavitha, On $2$ and $3$-rainbow domination number of circulant graph $G(n;\pm\\{1,2,3\\})$, Inter. J. Math. and Computer Science, 15 (2020) 661-–670.
  * [6] M. Furuya, M. Koyanagi, M. Yokota, Upper bound on $3$-rainbow domination in graphs with minimum degree $2$, Discrete Optim. 29 (2018) 45–76.
  * [7] H. Gao, C. Xi, Y. Yang, The $3$-rainbow domination number of the cartesian product of cycles, Mathematics 8 (2020) 65.
  * [8] T. Hamada, I. Yoshimura, Traversability and connectivity of middle graph of a graph, Discrete Math. 14 (1976) 247–255.
  * [9] K. Kim, Italian, $2$-rainbow and Roman domination numbers in middle graphs, submitted.
  * [10] Z.H. Shao, M.L. Liang, C. Yin, X.D. Xu, P. Pavlic, J. Zerovnik, On rainbow domination numbers of graphs, Inform. Sci. 254 (2014) 225-–234.
  * [11] S.M. Sheikholeslami, L. Volkmann, The $k$-rainbow domatic number of a graph, Discuss. Math. Graph Theory 32 (2012) 129–140.
  * [12] Y. Wang, X.L. Wu, N. Dehgardi, J. Amjadi, R. Khoeilar, J.B. Liu, $k$-rainbow domination number of $P_{3}\square P_{n}$, Mathematics 7 (2019) 203.